Make ControlFlowChecker follow the dataflow analysis idiom more closely

This makes ControlFlowInfo an ADT handling its own join operation, and combines the list of return statements into that structure. This is less error-prone if a new field is added, and helps simplify the logic in visit(IfStatement).

The invariants regarding the cf field are also clarified: It is "transferred" (in dataflow analysis terminology) from the point before the node to the point after the node by the visit() function. It is also undefined (null) outside of a function definition.

There's a cost to this CL in terms of LOC and maybe even memory allocations, but I suspect that's outweighed by sticking to a known paradigm for flow analysis.

RELNOTES: None
PiperOrigin-RevId: 167005045

3 files changed, 120 insertions, 31 deletions

diff --git a/src/tools/skylark/java/com/google/devtools/skylark/skylint/ControlFlowChecker.java b/src/tools/skylark/java/com/google/devtools/skylark/skylint/ControlFlowChecker.java
index 355069a6bf..e11c3d2a5f 100644
--- a/src/tools/skylark/java/com/google/devtools/skylark/skylint/ControlFlowChecker.java
+++ b/src/tools/skylark/java/com/google/devtools/skylark/skylint/ControlFlowChecker.java
@@ -14,6 +14,7 @@
 
 package com.google.devtools.skylark.skylint;
 
+import com.google.common.base.Preconditions;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
 import com.google.devtools.build.lib.syntax.Expression;
 import com.google.devtools.build.lib.syntax.ExpressionStatement;
@@ -26,8 +27,10 @@ import com.google.devtools.build.lib.syntax.ReturnStatement;
 import com.google.devtools.build.lib.syntax.Statement;
 import com.google.devtools.build.lib.syntax.SyntaxTreeVisitor;
 import java.util.ArrayList;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.stream.Stream;
+import javax.annotation.Nullable;
 
 /**
  * Performs lints related to control flow.
@@ -38,8 +41,19 @@ import java.util.stream.Stream;
 // TODO(skylark-team): Check for unreachable statements
 public class ControlFlowChecker extends SyntaxTreeVisitor {
   private final List<Issue> issues = new ArrayList<>();
-  private ControlFlowInfo cf = new ControlFlowInfo();
-  private List<ReturnStatement> returnStatementsWithoutValue = new ArrayList<>();
+
+  /**
+   * Represents the analyzed info at the current program point. The {@code visit()} methods
+   * implement the transfer function from the program point immediately before that AST node to the
+   * program point immediately after that node. This destructively consumes (modifies) the CFI
+   * object, so for branching nodes a copy must be made.
+   *
+   * <p>See also: https://en.wikipedia.org/wiki/Data-flow_analysis
+   *
+   * <p>This is always null whenever we're not in a function definition.
+   */
+  @Nullable
+  private ControlFlowInfo cfi = null;
 
   public static List<Issue> check(BuildFileAST ast) {
     ControlFlowChecker checker = new ControlFlowChecker();
@@ -49,41 +63,45 @@ public class ControlFlowChecker extends SyntaxTreeVisitor {
 
   @Override
   public void visit(IfStatement node) {
-    ControlFlowInfo saved = cf;
-    boolean someBranchHasReturnWithValue = false;
-    boolean someBranchHasReturnWithoutValue = false;
-    boolean allBranchesReturnAlwaysExplicitly = true;
+    if (cfi == null) {
+      return;
+    }
+    // Save the input cfi, copy its state to seed each branch, then gather the branches together
+    // with a join operation to produces the output cfi.
+    ControlFlowInfo input = cfi;
+    ArrayList<ControlFlowInfo> outputs = new ArrayList<>();
     Stream<List<Statement>> branches =
         Stream.concat(
             node.getThenBlocks().stream().map(ConditionalStatements::getStatements),
             Stream.of(node.getElseBlock()));
     for (List<Statement> branch : (Iterable<List<Statement>>) branches::iterator) {
-      cf = new ControlFlowInfo();
+      cfi = ControlFlowInfo.copy(input);
       visitAll(branch);
-      someBranchHasReturnWithValue |= cf.hasReturnWithValue;
-      someBranchHasReturnWithoutValue |= cf.hasReturnWithoutValue;
-      allBranchesReturnAlwaysExplicitly &= cf.returnsAlwaysExplicitly;
+      outputs.add(cfi);
     }
-    cf.hasReturnWithValue = saved.hasReturnWithValue || someBranchHasReturnWithValue;
-    cf.hasReturnWithoutValue = saved.hasReturnWithoutValue || someBranchHasReturnWithoutValue;
-    cf.returnsAlwaysExplicitly = saved.returnsAlwaysExplicitly || allBranchesReturnAlwaysExplicitly;
+    cfi = ControlFlowInfo.join(outputs);
   }
 
   @Override
   public void visit(ReturnStatement node) {
-    cf.returnsAlwaysExplicitly = true;
+    // Should be rejected by parser, but we may have been fed a bad AST.
+    Preconditions.checkState(cfi != null, "AST has illegal top-level return statement");
+    cfi.returnsAlwaysExplicitly = true;
     if (node.getReturnExpression() != null) {
-      cf.hasReturnWithValue = true;
+      cfi.hasReturnWithValue = true;
     } else {
-      cf.hasReturnWithoutValue = true;
-      returnStatementsWithoutValue.add(node);
+      cfi.hasReturnWithoutValue = true;
+      cfi.returnStatementsWithoutValue.add(new Return(node));
     }
   }
 
   @Override
   public void visit(ExpressionStatement node) {
+    if (cfi == null) {
+      return;
+    }
     if (isFail(node.getExpression())) {
-      cf.returnsAlwaysExplicitly = true;
+      cfi.returnsAlwaysExplicitly = true;
     }
   }
 
@@ -97,26 +115,92 @@ public class ControlFlowChecker extends SyntaxTreeVisitor {
 
   @Override
   public void visit(FunctionDefStatement node) {
-    cf = new ControlFlowInfo();
-    returnStatementsWithoutValue = new ArrayList<>();
+    Preconditions.checkState(cfi == null);
+    cfi = ControlFlowInfo.entry();
     super.visit(node);
-    if (cf.hasReturnWithValue && (!cf.returnsAlwaysExplicitly || cf.hasReturnWithoutValue)) {
+    if (cfi.hasReturnWithValue && (!cfi.returnsAlwaysExplicitly || cfi.hasReturnWithoutValue)) {
       issues.add(
           new Issue(
               "some but not all execution paths of '" + node.getIdentifier() + "' return a value",
               node.getLocation()));
-      for (ReturnStatement returnStatement : returnStatementsWithoutValue) {
+      for (Return returnWrapper : cfi.returnStatementsWithoutValue) {
         issues.add(
             new Issue(
                 "return value missing (you can `return None` if this is desired)",
-                returnStatement.getLocation()));
+                returnWrapper.node.getLocation()));
+      }
+    }
+    cfi = null;
+  }
+
+  /**
+   * Wrapper around {@code ReturnStatement} that supports hashing and equality based on the
+   * identity of the node it wraps.
+   */
+  private static class Return {
+
+    final ReturnStatement node;
+
+    Return(ReturnStatement node) {
+      this.node = node;
+    }
+
+    @Override
+    public boolean equals(Object other) {
+      if (!(other instanceof Return)) {
+        return false;
       }
+      return this.node == ((Return) other).node;
+    }
+
+    @Override
+    public int hashCode() {
+      return System.identityHashCode(node);
     }
   }
 
   private static class ControlFlowInfo {
-    boolean hasReturnWithValue = false;
-    boolean hasReturnWithoutValue = false;
-    boolean returnsAlwaysExplicitly = false;
+    private boolean hasReturnWithValue;
+    private boolean hasReturnWithoutValue;
+    private boolean returnsAlwaysExplicitly;
+    private final LinkedHashSet<Return> returnStatementsWithoutValue;
+
+    private ControlFlowInfo(
+        boolean hasReturnWithValue,
+        boolean hasReturnWithoutValue,
+        boolean returnsAlwaysExplicitly,
+        LinkedHashSet<Return> returnStatementsWithoutValue) {
+      this.hasReturnWithValue = hasReturnWithValue;
+      this.hasReturnWithoutValue = hasReturnWithoutValue;
+      this.returnsAlwaysExplicitly = returnsAlwaysExplicitly;
+      this.returnStatementsWithoutValue = returnStatementsWithoutValue;
+    }
+
+    /** Create a CFI corresponding to an entry point in the control-flow graph. */
+    static ControlFlowInfo entry() {
+      return new ControlFlowInfo(false, false, false, new LinkedHashSet<>());
+    }
+
+    /** Creates a copy of a CFI, including the {@code returnStatementsWithoutValue} collection. */
+    static ControlFlowInfo copy(ControlFlowInfo existing) {
+      return new ControlFlowInfo(
+          existing.hasReturnWithValue,
+          existing.hasReturnWithoutValue,
+          existing.returnsAlwaysExplicitly,
+          new LinkedHashSet<>(existing.returnStatementsWithoutValue));
+    }
+
+    /** Joins the CFIs for several alternative paths together. */
+    static ControlFlowInfo join(List<ControlFlowInfo> infos) {
+      ControlFlowInfo result = new ControlFlowInfo(
+          false, false, true, new LinkedHashSet<>());
+      for (ControlFlowInfo info : infos) {
+        result.hasReturnWithValue |= info.hasReturnWithValue;
+        result.hasReturnWithoutValue |= info.hasReturnWithoutValue;
+        result.returnsAlwaysExplicitly &= info.returnsAlwaysExplicitly;
+        result.returnStatementsWithoutValue.addAll(info.returnStatementsWithoutValue);
+      }
+      return result;
+    }
   }
 }
diff --git a/src/tools/skylark/java/com/google/devtools/skylark/skylint/Skylint.java b/src/tools/skylark/java/com/google/devtools/skylark/skylint/Skylint.java
index b9eb83f73a..92e2f5ae1d 100644
--- a/src/tools/skylark/java/com/google/devtools/skylark/skylint/Skylint.java
+++ b/src/tools/skylark/java/com/google/devtools/skylark/skylint/Skylint.java
@@ -41,11 +41,9 @@ public class Skylint {
     issues.sort(Issue::compare);
     if (!issues.isEmpty()) {
       System.out.println(path);
-    }
-    for (Issue issue : issues) {
-      System.out.println(issue);
-    }
-    if (!issues.isEmpty()) {
+      for (Issue issue : issues) {
+        System.out.println(issue);
+      }
       System.exit(1);
     }
   }
diff --git a/src/tools/skylark/javatests/com/google/devtools/skylark/skylint/ControlFlowCheckerTest.java b/src/tools/skylark/javatests/com/google/devtools/skylark/skylint/ControlFlowCheckerTest.java
index 7e7addd8a2..0b00745ff2 100644
--- a/src/tools/skylark/javatests/com/google/devtools/skylark/skylint/ControlFlowCheckerTest.java
+++ b/src/tools/skylark/javatests/com/google/devtools/skylark/skylint/ControlFlowCheckerTest.java
@@ -35,6 +35,13 @@ public class ControlFlowCheckerTest {
   }
 
   @Test
+  public void testAnalyzerToleratesTopLevelFail() throws Exception {
+    Truth.assertThat(
+            findIssues("fail(\"fail is considered a return, but not at the top level\")"))
+        .isEmpty();
+  }
+
+  @Test
   public void testIfElseReturnMissing() throws Exception {
     Truth.assertThat(
             findIssues(