path: root/src/tools/skylark/java/com/google/devtools/skylark/skylint/UsageChecker.java

// 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.base.Equivalence;
import com.google.common.base.Equivalence.Wrapper;
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.AssignmentStatement;
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.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.LinkedHashSet;
import java.util.List;
import java.util.Set;

/** Checks that every import, private function or variable definition is used somewhere. */
public class UsageChecker extends AstVisitorWithNameResolution {
  private static final String UNUSED_BINDING_CATEGORY = "unused-binding";
  private static final String UNINITIALIZED_VARIABLE_CATEGORY = "uninitialized-variable";

  private final List<Issue> issues = new ArrayList<>();
  private UsageInfo ui = UsageInfo.empty();
  private final SetMultimap<Integer, Wrapper<ASTNode>> idToAllDefinitions =
      LinkedHashMultimap.create();
  private final Set<Wrapper<ASTNode>> initializationsWithNone = new LinkedHashSet<>();

  public static List<Issue> check(BuildFileAST ast) {
    UsageChecker checker = new UsageChecker();
    checker.visit(ast);
    return checker.issues;
  }

  @Override
  public void visit(FunctionDefStatement node) {
    UsageInfo saved = ui.copy();
    super.visit(node);
    ui = UsageInfo.join(Arrays.asList(saved, ui));
  }

  @Override
  public void visit(IfStatement node) {
    UsageInfo input = ui;
    List<UsageInfo> outputs = new ArrayList<>();
    for (ConditionalStatements clause : node.getThenBlocks()) {
      ui = input.copy();
      visit(clause);
      outputs.add(ui);
    }
    ui = input.copy();
    visitBlock(node.getElseBlock());
    outputs.add(ui);
    ui = UsageInfo.join(outputs);
  }

  @Override
  public void visit(ForStatement node) {
    visit(node.getCollection());
    visit(node.getVariable());
    UsageInfo noIteration = ui.copy();
    visitBlock(node.getBlock());
    UsageInfo oneIteration = ui.copy();
    // We need to visit the block again in case a variable was reassigned in the last iteration and
    // the new value isn't used until the next iteration
    visit(node.getVariable());
    visitBlock(node.getBlock());
    UsageInfo manyIterations = ui.copy();
    ui = UsageInfo.join(Arrays.asList(noIteration, oneIteration, manyIterations));
  }

  @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;
    }
  }

  @Override
  public void visit(AssignmentStatement node) {
    super.visit(node);
    /* If a variable is initialized with None, and there exist other assignments to the variable,
     * then this initialization is itself considered as a usage. This is because it's good practice
     * to place a "declaration" of a variable in a location that dominates all its uses, especially
     * so if you want to document the variable. Example:
     *
     *     var = None  # don't warn about the unused binding
     *     if condition:
     *       var = 0
     *     else:
     *       var = 1
     *
     * Unfortunately, as a side-effect, the following won't trigger a warning either:
     *
     *     var = None  # doesn't warn either but ideally should
     *     var = 0
     */
    Expression lhs = node.getLValue().getExpression();
    Expression rhs = node.getExpression();
    if (lhs instanceof Identifier
        && rhs instanceof Identifier
        && ((Identifier) rhs).getName().equals("None")) {
      NameInfo info = env.resolveName(((Identifier) lhs).getName());
      // if it's an initialization:
      if (info != null && idToAllDefinitions.get(info.id).size() == 1) {
        initializationsWithNone.add(wrapNode(lhs));
      }
    }
  }

  private void defineIdentifier(NameInfo name, ASTNode node) {
    ui.idToLastDefinitions.removeAll(name.id);
    ui.idToLastDefinitions.put(name.id, wrapNode(node));
    ui.initializedIdentifiers.add(name.id);
    idToAllDefinitions.put(name.id, wrapNode(node));
  }

  @Override
  protected void use(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) {
    NameInfo info = env.resolveExistingName(name);
    defineIdentifier(info, node);
  }

  @Override
  protected void reassign(Identifier ident) {
    declare(ident.getName(), ident);
  }

  @Override
  public void exitBlock() {
    Collection<Integer> ids = env.getNameIdsInCurrentBlock();
    for (Integer id : ids) {
      checkUsed(id);
    }
    super.exitBlock();
  }

  private void checkUsed(Integer id) {
    Set<Wrapper<ASTNode>> unusedDefinitions = new LinkedHashSet<>(idToAllDefinitions.get(id));
    unusedDefinitions.removeAll(ui.usedDefinitions);
    NameInfo nameInfo = env.getNameInfo(id);
    String name = nameInfo.name;
    if ("_".equals(name) || nameInfo.kind == Kind.BUILTIN) {
      return;
    }
    if ((nameInfo.kind == Kind.LOCAL || nameInfo.kind == Kind.PARAMETER)
        && (name.startsWith("_") || name.startsWith("unused_") || name.startsWith("UNUSED_"))) {
      // local variables starting with an underscore need not be used
      return;
    }
    if ((nameInfo.kind == Kind.GLOBAL || nameInfo.kind == Kind.FUNCTION) && !name.startsWith("_")) {
      // symbol might be loaded in another file
      return;
    }
    String message = "unused binding of '" + name + "'";
    if (nameInfo.kind == Kind.IMPORTED && !nameInfo.name.startsWith("_")) {
      message +=
          ". If you want to re-export a symbol, use the following pattern:\n"
              + "\n"
              + "load(..., _"
              + name
              + " = '"
              + name
              + "', ...)\n"
              + name
              + " = _"
              + name
              + "\n"
              + "\n"
              + "More details in the documentation.";
    } else if (nameInfo.kind == Kind.PARAMETER) {
      message +=
          ". If this is intentional, "
              + "you can add `_ignore = [<param1>, <param2>, ...]` to the function body.";
    } else if (nameInfo.kind == Kind.LOCAL) {
      message += ". If this is intentional, you can use '_' or rename it to '_" + name + "'.";
    }
    for (Wrapper<ASTNode> definition : unusedDefinitions) {
      if (initializationsWithNone.contains(definition) && idToAllDefinitions.get(id).size() > 1) {
        // initializations with None are OK, cf. visit(AssignmentStatement) above
        continue;
      }
      issues.add(
          Issue.create(UNUSED_BINDING_CATEGORY, message, unwrapNode(definition).getLocation()));
    }
  }

  private void checkInitialized(NameInfo info, Identifier node) {
    if (ui.reachable && !ui.initializedIdentifiers.contains(info.id) && info.kind != Kind.BUILTIN) {
      issues.add(
          Issue.create(
              UNINITIALIZED_VARIABLE_CATEGORY,
              "variable '"
                  + info.name
                  + "' may not have been initialized."
                  + " If you believe this is wrong, you can add `fail('unreachable')"
                  + " to the branches where it is not initialized"
                  + " or initialize it with `None` at the beginning."
                  + " For more details, have a look at the documentation.",
              node.getLocation()));
    }
  }

  private static class UsageInfo {
    /**
     * Stores for each variable ID the definitions that are "live", i.e. are the most recent ones on
     * some execution path.
     *
     * <p>There can be more than one last definition if branches are involved, e.g. if foo: x = 1;
     * else x = 2;
     */
    private final SetMultimap<Integer, Wrapper<ASTNode>> idToLastDefinitions;
    /** Set of definitions that have already been used at some point. */
    private final Set<Wrapper<ASTNode>> 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, Wrapper<ASTNode>> idToLastDefinitions,
        Set<Wrapper<ASTNode>> 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 LinkedHashSet<>(), new LinkedHashSet<>(), true);
    }

    UsageInfo copy() {
      return new UsageInfo(
          LinkedHashMultimap.create(idToLastDefinitions),
          new LinkedHashSet<>(usedDefinitions),
          new LinkedHashSet<>(initializedIdentifiers),
          reachable);
    }

    static UsageInfo join(Collection<UsageInfo> uis) {
      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;
    }
  }

  private Wrapper<ASTNode> wrapNode(ASTNode node) {
    return Equivalence.identity().wrap(node);
  }

  private ASTNode unwrapNode(Wrapper<ASTNode> wrapper) {
    return wrapper.get();
  }
}