Skylint: add lint for uninitialized variables

RELNOTES: none
PiperOrigin-RevId: 167614625

3 files changed, 200 insertions, 32 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 a75a4905f8..4fb733f523 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
@@ -139,7 +139,7 @@ public class ControlFlowChecker extends SyntaxTreeVisitor {
     }
   }
 
-  private boolean isFail(Expression expression) {
+  public static boolean isFail(Expression expression) {
     if (expression instanceof FuncallExpression) {
       Expression function = ((FuncallExpression) expression).getFunction();
       return function instanceof Identifier && ((Identifier) function).getName().equals("fail");
diff --git a/src/tools/skylark/java/com/google/devtools/skylark/skylint/UsageChecker.java b/src/tools/skylark/java/com/google/devtools/skylark/skylint/UsageChecker.java
index a464e2645d..1376e82391 100644
--- a/src/tools/skylark/java/com/google/devtools/skylark/skylint/UsageChecker.java
+++ b/src/tools/skylark/java/com/google/devtools/skylark/skylint/UsageChecker.java
@@ -17,19 +17,24 @@ package com.google.devtools.skylark.skylint;
 import com.google.common.collect.LinkedHashMultimap;
 import com.google.common.collect.SetMultimap;
 import com.google.devtools.build.lib.syntax.ASTNode;
+import com.google.devtools.build.lib.syntax.AugmentedAssignmentStatement;
 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.FlowStatement;
 import com.google.devtools.build.lib.syntax.ForStatement;
+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.ListLiteral;
+import com.google.devtools.build.lib.syntax.ReturnStatement;
 import com.google.devtools.skylark.skylint.Environment.NameInfo;
 import com.google.devtools.skylark.skylint.Environment.NameInfo.Kind;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
-import java.util.HashSet;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Set;
 import javax.annotation.Nullable;
@@ -51,13 +56,16 @@ public class UsageChecker extends AstVisitorWithNameResolution {
   }
 
   @Override
-  public void visit(Identifier node) {
+  public void visit(FunctionDefStatement node) {
+    UsageInfo saved = ui.copy();
     super.visit(node);
-    NameInfo info = env.resolveName(node.getName());
-    // TODO(skylark-team): Don't ignore unresolved symbols in the future but report an error
-    if (info != null) {
-      ui.usedDefinitions.addAll(ui.idToLastDefinitions.get(info.id));
-    }
+    ui = UsageInfo.join(Arrays.asList(saved, ui));
+  }
+
+  @Override
+  public void visit(Identifier identifier) {
+    super.visit(identifier);
+    useIdentifier(identifier);
   }
 
   @Override
@@ -104,11 +112,52 @@ public class UsageChecker extends AstVisitorWithNameResolution {
   }
 
   @Override
+  public void visit(AugmentedAssignmentStatement node) {
+    for (Identifier ident : node.getLValue().boundIdentifiers()) {
+      useIdentifier(ident);
+    }
+    super.visit(node);
+  }
+
+  @Override
+  public void visit(FlowStatement node) {
+    ui.reachable = false;
+  }
+
+  @Override
+  public void visit(ReturnStatement node) {
+    super.visit(node);
+    ui.reachable = false;
+  }
+
+  @Override
+  public void visit(ExpressionStatement node) {
+    super.visit(node);
+    if (ControlFlowChecker.isFail(node.getExpression())) {
+      ui.reachable = false;
+    }
+  }
+
+  private void defineIdentifier(NameInfo name, ASTNode node) {
+    ui.idToLastDefinitions.removeAll(name.id);
+    ui.idToLastDefinitions.put(name.id, new Node(node));
+    ui.initializedIdentifiers.add(name.id);
+    idToAllDefinitions.put(name.id, new Node(node));
+  }
+
+  private void useIdentifier(Identifier identifier) {
+    NameInfo info = env.resolveName(identifier.getName());
+    // TODO(skylark-team): Don't ignore unresolved symbols in the future but report an error
+    if (info != null) {
+      ui.usedDefinitions.addAll(ui.idToLastDefinitions.get(info.id));
+      checkInitialized(info, identifier);
+    }
+  }
+
+  @Override
   protected void declare(String name, ASTNode node) {
-    int id = env.resolveExistingName(name).id;
-    ui.idToLastDefinitions.removeAll(id);
-    ui.idToLastDefinitions.put(id, new Node(node));
-    idToAllDefinitions.put(id, new Node(node));
+    NameInfo info = env.resolveExistingName(name);
+    defineIdentifier(info, node);
   }
 
   @Override
@@ -154,6 +203,14 @@ public class UsageChecker extends AstVisitorWithNameResolution {
     }
   }
 
+  private void checkInitialized(NameInfo info, Identifier node) {
+    if (ui.reachable && !ui.initializedIdentifiers.contains(info.id) && info.kind != Kind.BUILTIN) {
+      issues.add(
+          new Issue(
+              "identifier '" + info.name + "' may not have been initialized", node.getLocation()));
+    }
+  }
+
   private static class UsageInfo {
     /**
      * Stores for each variable ID the definitions that are "live", i.e. are the most recent ones on
@@ -165,26 +222,61 @@ public class UsageChecker extends AstVisitorWithNameResolution {
     private final SetMultimap<Integer, Node> idToLastDefinitions;
     /** Set of definitions that have already been used at some point. */
     private final Set<Node> usedDefinitions;
+    /** Set of variable IDs that are initialized. */
+    private final Set<Integer> initializedIdentifiers;
+    /**
+     * Whether the current position in the program is reachable.
+     *
+     * <p>This is needed to correctly compute initialized variables.
+     */
+    private boolean reachable;
 
-    private UsageInfo(SetMultimap<Integer, Node> idToLastDefinitions, Set<Node> usedDefinitions) {
+    private UsageInfo(
+        SetMultimap<Integer, Node> idToLastDefinitions,
+        Set<Node> usedDefinitions,
+        Set<Integer> initializedIdentifiers,
+        boolean reachable) {
       this.idToLastDefinitions = idToLastDefinitions;
       this.usedDefinitions = usedDefinitions;
+      this.initializedIdentifiers = initializedIdentifiers;
+      this.reachable = reachable;
     }
 
     static UsageInfo empty() {
-      return new UsageInfo(LinkedHashMultimap.create(), new HashSet<>());
+      return new UsageInfo(
+          LinkedHashMultimap.create(), new LinkedHashSet<>(), new LinkedHashSet<>(), true);
     }
 
     UsageInfo copy() {
       return new UsageInfo(
-          LinkedHashMultimap.create(idToLastDefinitions), new HashSet<>(usedDefinitions));
+          LinkedHashMultimap.create(idToLastDefinitions),
+          new LinkedHashSet<>(usedDefinitions),
+          new LinkedHashSet<>(initializedIdentifiers),
+          reachable);
     }
 
     static UsageInfo join(Collection<UsageInfo> uis) {
-      UsageInfo result = UsageInfo.empty();
+      Set<Integer> initializedInRelevantBranch = new LinkedHashSet<>();
+      for (UsageInfo ui : uis) {
+        if (ui.reachable) {
+          initializedInRelevantBranch = ui.initializedIdentifiers;
+          break;
+        }
+      }
+      UsageInfo result =
+          new UsageInfo(
+              LinkedHashMultimap.create(),
+              new LinkedHashSet<>(),
+              initializedInRelevantBranch,
+              false);
       for (UsageInfo ui : uis) {
         result.idToLastDefinitions.putAll(ui.idToLastDefinitions);
         result.usedDefinitions.addAll(ui.usedDefinitions);
+        if (ui.reachable) {
+          // Only a non-diverging branch can affect the set of initialized variables.
+          result.initializedIdentifiers.retainAll(ui.initializedIdentifiers);
+        }
+        result.reachable |= ui.reachable;
       }
       return result;
     }
diff --git a/src/tools/skylark/javatests/com/google/devtools/skylark/skylint/UsageCheckerTest.java b/src/tools/skylark/javatests/com/google/devtools/skylark/skylint/UsageCheckerTest.java
index 6251921143..1b78069fc7 100644
--- a/src/tools/skylark/javatests/com/google/devtools/skylark/skylint/UsageCheckerTest.java
+++ b/src/tools/skylark/javatests/com/google/devtools/skylark/skylint/UsageCheckerTest.java
@@ -44,6 +44,13 @@ public class UsageCheckerTest {
   }
 
   @Test
+  public void reportUnusedGlobals() throws Exception {
+    String message = findIssues("_UNUSED = len([])", "def _unused(): pass").toString();
+    Truth.assertThat(message).contains(":1:1: unused definition of '_UNUSED'");
+    Truth.assertThat(message).contains(":2:5: unused definition of '_unused'");
+  }
+
+  @Test
   public void reportUnusedLocals() throws Exception {
     String message = findIssues("def some_function(param):", "  local, local2 = 1, 3").toString();
     Truth.assertThat(message).contains(":1:19: unused definition of 'param'");
@@ -82,17 +89,9 @@ public class UsageCheckerTest {
   }
 
   @Test
-  public void reportUnusedGlobals() throws Exception {
-    String message = findIssues("_UNUSED = len([])", "def _unused(): pass").toString();
-    Truth.assertThat(message).contains(":1:1: unused definition of '_UNUSED'");
-    Truth.assertThat(message).contains(":2:5: unused definition of '_unused'");
-  }
-
-  @Test
   public void reportReassignedUnusedVariable() throws Exception {
-    Truth.assertThat(
-            findIssues("def some_function():", "  x = 1", "  print(x)", "  x += 2").toString())
-        .contains(":4:3: unused definition of 'x'");
+    Truth.assertThat(findIssues("def some_function():", "  x = 1", "  x += 2").toString())
+        .contains(":3:3: unused definition of 'x'");
   }
 
   @Test
@@ -123,6 +122,82 @@ public class UsageCheckerTest {
   }
 
   @Test
+  public void reportUninitializedAfterIfElifElse() throws Exception {
+    String message =
+        findIssues(
+                "def some_function(a, b):",
+                "  if a:",
+                "    y = 2",
+                "  elif b:",
+                "    pass",
+                "  else:",
+                "    y = 1",
+                "  y += 2",
+                "  print(y)")
+            .toString();
+    Truth.assertThat(message).contains(":8:3: identifier 'y' may not have been initialized");
+  }
+
+  @Test
+  public void reportUninitializedAfterForLoop() throws Exception {
+    String message =
+        findIssues("def some_function():", "  for _ in []:", "    y = 1", "  print(y)").toString();
+    Truth.assertThat(message).contains(":4:9: identifier 'y' may not have been initialized");
+  }
+
+  @Test
+  public void dontReportAlwaysInitializedInNestedIf() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                "def some_function(a, b):",
+                "  if a:",
+                "    if b:",
+                "      x = b",
+                "    else:",
+                "      x = a",
+                "  else:",
+                "    x = not a",
+                "  return x"))
+        .isEmpty();
+  }
+
+  @Test
+  public void dontReportAlwaysInitializedBecauseUnreachable() throws Exception {
+    Truth.assertThat(
+            findIssues(
+                "def some_function(a, b):",
+                "  if a:",
+                "    y = 1",
+                "  elif b:",
+                "    return",
+                "  else:",
+                "    fail('fail')",
+                "  print(y)",
+                "  for _ in []:",
+                "    if a:",
+                "      break",
+                "    elif b:",
+                "      continue",
+                "    else:",
+                "      z = 2",
+                "    print(z)"))
+        .isEmpty();
+  }
+
+  @Test
+  public void dontReportUsedAsParameterDefault() throws Exception {
+    Truth.assertThat(
+        findIssues(
+            "_x = 1",
+            "def foo(y=_x):",
+            "  print(y)",
+            "",
+            "foo()"
+        )
+    ).isEmpty();
+  }
+
+  @Test
   public void dontReportUsedAfterIf() throws Exception {
     Truth.assertThat(
             findIssues(
@@ -142,11 +217,11 @@ public class UsageCheckerTest {
                 "  x = 0",
                 "  for _ in []:",
                 "    print(x)",
-                "    x += 1"))
-        .isEmpty();
-    Truth.assertThat(
-            findIssues(
+                "    x += 1",
+                "  return x",
+                "",
                 "def foo():",
+                "    x = \"xyz\"",
                 "    for i in range(5):",
                 "        if i % 2 == 1:",
                 "            print(x)",
@@ -175,9 +250,10 @@ public class UsageCheckerTest {
     Truth.assertThat(
             findIssues(
                 "_GLOBAL = 0",
+                "def public_function():",
+                "  _global_function(_GLOBAL)",
                 "def _global_function(param):",
-                "  print(param)",
-                "_global_function(_GLOBAL)"))
+                "  print(param)"))
         .isEmpty();
   }