Add a lint for missing return statements

This lint checks that if a functions returns a value in some execution
paths, it does so in all execution paths.

RELNOTES: None
PiperOrigin-RevId: 166688783

4 files changed, 366 insertions, 4 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
new file mode 100644
index 0000000000..355069a6bf
--- /dev/null
+++ b/src/tools/skylark/java/com/google/devtools/skylark/skylint/ControlFlowChecker.java
@@ -0,0 +1,122 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.skylark.skylint;
+
+import com.google.devtools.build.lib.syntax.BuildFileAST;
+import com.google.devtools.build.lib.syntax.Expression;
+import com.google.devtools.build.lib.syntax.ExpressionStatement;
+import com.google.devtools.build.lib.syntax.FuncallExpression;
+import com.google.devtools.build.lib.syntax.FunctionDefStatement;
+import com.google.devtools.build.lib.syntax.Identifier;
+import com.google.devtools.build.lib.syntax.IfStatement;
+import com.google.devtools.build.lib.syntax.IfStatement.ConditionalStatements;
+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.List;
+import java.util.stream.Stream;
+
+/**
+ * Performs lints related to control flow.
+ *
+ * <p>For now, it only checks that if a function returns a value in some execution paths, it does so
+ * in all execution paths.
+ */
+// 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<>();
+
+  public static List<Issue> check(BuildFileAST ast) {
+    ControlFlowChecker checker = new ControlFlowChecker();
+    checker.visit(ast);
+    return checker.issues;
+  }
+
+  @Override
+  public void visit(IfStatement node) {
+    ControlFlowInfo saved = cf;
+    boolean someBranchHasReturnWithValue = false;
+    boolean someBranchHasReturnWithoutValue = false;
+    boolean allBranchesReturnAlwaysExplicitly = true;
+    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();
+      visitAll(branch);
+      someBranchHasReturnWithValue |= cf.hasReturnWithValue;
+      someBranchHasReturnWithoutValue |= cf.hasReturnWithoutValue;
+      allBranchesReturnAlwaysExplicitly &= cf.returnsAlwaysExplicitly;
+    }
+    cf.hasReturnWithValue = saved.hasReturnWithValue || someBranchHasReturnWithValue;
+    cf.hasReturnWithoutValue = saved.hasReturnWithoutValue || someBranchHasReturnWithoutValue;
+    cf.returnsAlwaysExplicitly = saved.returnsAlwaysExplicitly || allBranchesReturnAlwaysExplicitly;
+  }
+
+  @Override
+  public void visit(ReturnStatement node) {
+    cf.returnsAlwaysExplicitly = true;
+    if (node.getReturnExpression() != null) {
+      cf.hasReturnWithValue = true;
+    } else {
+      cf.hasReturnWithoutValue = true;
+      returnStatementsWithoutValue.add(node);
+    }
+  }
+
+  @Override
+  public void visit(ExpressionStatement node) {
+    if (isFail(node.getExpression())) {
+      cf.returnsAlwaysExplicitly = true;
+    }
+  }
+
+  private boolean isFail(Expression expression) {
+    if (expression instanceof FuncallExpression) {
+      Expression function = ((FuncallExpression) expression).getFunction();
+      return function instanceof Identifier && ((Identifier) function).getName().equals("fail");
+    }
+    return false;
+  }
+
+  @Override
+  public void visit(FunctionDefStatement node) {
+    cf = new ControlFlowInfo();
+    returnStatementsWithoutValue = new ArrayList<>();
+    super.visit(node);
+    if (cf.hasReturnWithValue && (!cf.returnsAlwaysExplicitly || cf.hasReturnWithoutValue)) {
+      issues.add(
+          new Issue(
+              "some but not all execution paths of '" + node.getIdentifier() + "' return a value",
+              node.getLocation()));
+      for (ReturnStatement returnStatement : returnStatementsWithoutValue) {
+        issues.add(
+            new Issue(
+                "return value missing (you can `return None` if this is desired)",
+                returnStatement.getLocation()));
+      }
+    }
+  }
+
+  private static class ControlFlowInfo {
+    boolean hasReturnWithValue = false;
+    boolean hasReturnWithoutValue = false;
+    boolean returnsAlwaysExplicitly = false;
+  }
+}
diff --git a/src/tools/skylark/java/com/google/devtools/skylark/skylint/Issue.java b/src/tools/skylark/java/com/google/devtools/skylark/skylint/Issue.java
index 5192bf52f8..975798a9cc 100644
--- a/src/tools/skylark/java/com/google/devtools/skylark/skylint/Issue.java
+++ b/src/tools/skylark/java/com/google/devtools/skylark/skylint/Issue.java
@@ -31,4 +31,14 @@ public class Issue {
   public String toString() {
     return location + ": " + message;
   }
+
+  public static int compare(Issue i1, Issue i2) {
+    Location l1 = i1.location;
+    Location l2 = i2.location;
+    int pathComparison = l1.getPath().compareTo(l2.getPath());
+    if (pathComparison != 0) {
+      return pathComparison;
+    }
+    return l1.getStartOffset() - l2.getStartOffset();
+  }
 }
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 9b92698a28..dd91bb2e51 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
@@ -18,24 +18,34 @@ import com.google.devtools.build.lib.syntax.BuildFileAST;
 import java.io.IOException;
 import java.nio.charset.StandardCharsets;
 import java.nio.file.Files;
+import java.nio.file.Path;
 import java.nio.file.Paths;
+import java.util.ArrayList;
 import java.util.List;
 
 /** The main class for the skylint binary. */
 public class Skylint {
   public static void main(String[] args) throws IOException {
-    String content =
-        new String(
-            Files.readAllBytes(Paths.get(args[0]).toAbsolutePath()), StandardCharsets.ISO_8859_1);
+    Path path = Paths.get(args[0]).toAbsolutePath();
+    String content = new String(Files.readAllBytes(path), StandardCharsets.ISO_8859_1);
     BuildFileAST ast =
         BuildFileAST.parseSkylarkString(
             event -> {
               System.err.println(event);
             },
             content);
-    List<Issue> issues = NamingConventionsChecker.check(ast);
+    List<Issue> issues = new ArrayList<>();
+    issues.addAll(NamingConventionsChecker.check(ast));
+    issues.addAll(ControlFlowChecker.check(ast));
+    issues.sort(Issue::compare);
+    if (!issues.isEmpty()) {
+      System.out.println(path);
+    }
     for (Issue issue : issues) {
       System.out.println(issue);
     }
+    if (!issues.isEmpty()) {
+      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
new file mode 100644
index 0000000000..7e7addd8a2
--- /dev/null
+++ b/src/tools/skylark/javatests/com/google/devtools/skylark/skylint/ControlFlowCheckerTest.java
@@ -0,0 +1,220 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.skylark.skylint;
+
+import com.google.common.truth.Truth;
+import com.google.devtools.build.lib.syntax.BuildFileAST;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+@RunWith(JUnit4.class)
+public class ControlFlowCheckerTest {
+  private static List<Issue> findIssues(String... lines) {
+    String content = String.join("\n", lines);
+    BuildFileAST ast =
+        BuildFileAST.parseSkylarkString(
+            event -> {
+              throw new IllegalArgumentException(event.getMessage());
+            },
+            content);
+    return ControlFlowChecker.check(ast);
+  }
+
+  @Test
+  public void testIfElseReturnMissing() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                    "def some_function(x):",
+                    "  if x:",
+                    "    print('foo')",
+                    "  else:",
+                    "    return x")
+                .toString())
+        .contains("some but not all execution paths of 'some_function' return a value");
+  }
+
+  @Test
+  public void testIfElseReturnValueMissing() throws Exception {
+    String messages =
+        findIssues(
+                "def some_function(x):",
+                "  if x:",
+                "    return x",
+                "  else:",
+                "    return # missing value")
+            .toString();
+    Truth.assertThat(messages)
+        .contains("some but not all execution paths of 'some_function' return a value");
+    Truth.assertThat(messages).contains(":5:5: return value missing");
+  }
+
+  @Test
+  public void testIfElifElseReturnMissing() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                    "def f(x):",
+                    "  if x:",
+                    "    return x",
+                    "  elif not x:",
+                    "    pass",
+                    "  else:",
+                    "    return not x")
+                .toString())
+        .contains("some but not all execution paths of 'f' return a value");
+  }
+
+  @Test
+  public void testNestedIfElseReturnMissing() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                    "def f(x, y):",
+                    "  if x:",
+                    "    if y:",
+                    "      return y",
+                    "    else:",
+                    "      print('foo')",
+                    "  else:",
+                    "    return x")
+                .toString())
+        .contains("some but not all execution paths of 'f' return a value");
+  }
+
+  @Test
+  public void testElseBranchMissing() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                    "def some_function(x):",
+                    "  if x:",
+                    "    return x",
+                    "  elif not x:",
+                    "    return not x")
+                .toString())
+        .contains("some but not all execution paths of 'some_function' return a value");
+  }
+
+  @Test
+  public void testIfAndFallOffEnd() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                    "def some_function(x):",
+                    "  if x:",
+                    "    return x",
+                    "  print('foo')",
+                    "  # return missing here")
+                .toString())
+        .contains("some but not all execution paths of 'some_function' return a value");
+  }
+
+  @Test
+  public void testAlwaysReturnButSometimesWithoutValue() throws Exception {
+    String messages =
+        findIssues(
+                "def some_function(x):",
+                "  if x:",
+                "    return # returns without value here",
+                "  return x")
+            .toString();
+    Truth.assertThat(messages)
+        .contains("some but not all execution paths of 'some_function' return a value");
+    Truth.assertThat(messages).contains(":3:5: return value missing");
+  }
+
+  @Test
+  public void testIfBeforeReturn() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                "def f(x, y):",
+                "  if x:",
+                "    return x",
+                "  elif not y:",
+                "    print('foo')",
+                "  print('bar')",
+                "  return y"))
+        .isEmpty();
+  }
+
+  @Test
+  public void testReturnInAllBranches() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                "def f(x, y):",
+                "  if x:",
+                "    return x",
+                "  elif not y:",
+                "    return None",
+                "  else:",
+                "    return y"))
+        .isEmpty();
+  }
+
+  @Test
+  public void testReturnInNestedIf() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                "def f(x,y):",
+                "  if x:",
+                "    if y:",
+                "      return y",
+                "    else:",
+                "      return not y",
+                "  else:",
+                "    return not x"))
+        .isEmpty();
+  }
+
+  @Test
+  public void testIfStatementSequence() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                "def f(x,y):",
+                "  if x:",
+                "    print('foo')",
+                "  else:",
+                "    return x",
+                "  print('bar')",
+                "  if y:",
+                "    return x",
+                "  else:",
+                "    return y"))
+        .isEmpty();
+    Truth.assertThat(
+            findIssues(
+                "def f(x,y):",
+                "  if x:",
+                "    return x",
+                "  else:",
+                "    return x",
+                "  # from now on everything's unreachable",
+                "  print('bar')",
+                "  if y:",
+                "    return x",
+                "  # no else branch but doesn't matter since it's unreachable"))
+        .isEmpty();
+  }
+
+  @Test
+  public void testCallToFail() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                "def some_function_name(x):",
+                "  if x:",
+                "    fail('bar')",
+                "  else:",
+                "    return x"))
+        .isEmpty();
+  }
+}