uber / NullAway / #1105

/*

 * Copyright (c) 2017 Uber Technologies, Inc.

 *

 * Permission is hereby granted, free of charge, to any person obtaining a copy

 * of this software and associated documentation files (the "Software"), to deal

 * in the Software without restriction, including without limitation the rights

 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

 * copies of the Software, and to permit persons to whom the Software is

 * furnished to do so, subject to the following conditions:

 *

 * The above copyright notice and this permission notice shall be included in

 * all copies or substantial portions of the Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

 * THE SOFTWARE.

 */

package com.uber.nullaway.dataflow;

import static com.uber.nullaway.NullabilityUtil.castToNonNull;

import com.google.common.base.Preconditions;

import com.google.common.collect.ImmutableList;

import com.google.common.collect.ImmutableSet;

import com.google.errorprone.VisitorState;

import com.google.errorprone.util.ASTHelpers;

import com.sun.source.tree.LiteralTree;

import com.sun.source.tree.MethodInvocationTree;

import com.sun.source.tree.Tree;

import com.sun.tools.javac.code.Symbol;

import com.sun.tools.javac.code.Type;

import com.uber.nullaway.NullabilityUtil;

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.List;

import java.util.Objects;

import java.util.Set;

import javax.annotation.Nullable;

import javax.lang.model.element.Element;

import javax.lang.model.element.ElementKind;

import javax.lang.model.element.Modifier;

import javax.lang.model.element.VariableElement;

import org.checkerframework.nullaway.dataflow.cfg.node.FieldAccessNode;

import org.checkerframework.nullaway.dataflow.cfg.node.IntegerLiteralNode;

import org.checkerframework.nullaway.dataflow.cfg.node.LocalVariableNode;

import org.checkerframework.nullaway.dataflow.cfg.node.LongLiteralNode;

import org.checkerframework.nullaway.dataflow.cfg.node.MethodAccessNode;

import org.checkerframework.nullaway.dataflow.cfg.node.MethodInvocationNode;

import org.checkerframework.nullaway.dataflow.cfg.node.Node;

import org.checkerframework.nullaway.dataflow.cfg.node.StringLiteralNode;

import org.checkerframework.nullaway.dataflow.cfg.node.SuperNode;

import org.checkerframework.nullaway.dataflow.cfg.node.ThisNode;

import org.checkerframework.nullaway.dataflow.cfg.node.TypeCastNode;

import org.checkerframework.nullaway.dataflow.cfg.node.VariableDeclarationNode;

import org.checkerframework.nullaway.dataflow.cfg.node.WideningConversionNode;

import org.checkerframework.nullaway.javacutil.TreeUtils;

/**

 * Represents an extended notion of an access path, which we track for nullness.

 *

 * <p>Typically, access paths are of the form x.f.g.h, where x is a variable and f, g, and h are

 * field names. Here, we also allow no-argument methods to appear in the access path, as well as

 * method calls passed only statically constant parameters, so an AP can be of the form

 * x.f().g.h([int_expr|string_expr]) in general.

 *

 * <p>We do not allow array accesses in access paths for the moment.

 */

public final class AccessPath implements MapKey {

  /**

   * A prefix added for elements appearing in method invocation APs which represent fields that can

   * be proven to be class-initialization time constants (i.e. static final fields of a type known

   * to be structurally immutable, such as io.grpc.Metadata.Key).

   *

   * <p>This prefix helps avoid collisions between common field names and common strings, e.g.

   * "KEY_1" and the field KEY_1.

   */

  private static final String IMMUTABLE_FIELD_PREFIX = "static final [immutable] field: ";

  /**

   * Encode a static final field as a constant argument on a method's AccessPathElement

   *

   * <p>The field must be of a type known to be structurally immutable, in addition to being

   * declared static and final for this encoding to make any sense. We do not verify this here, and

   * rather operate only on the field's fully qualified name, as this is intended to be a quick

   * utility method.

   *

   * @param fieldFQN the field's Fully Qualified Name

   * @return a string suitable to be included as part of the constant arguments of an

   *     AccessPathElement, assuming the field is indeed static final and of an structurally

   *     immutable type

   */

  public static String immutableFieldNameAsConstantArgument(String fieldFQN) {

  }

  /** Root of the access path. If {@code null}, the root is the receiver argument */

  @Nullable private final Element root;

  private final ImmutableList<AccessPathElement> elements;

  /**

   * if present, the argument to the map get() method call that is the final element of this path

   */

  @Nullable private final MapKey mapGetArg;

  private AccessPath(@Nullable Element root, ImmutableList<AccessPathElement> elements) {

  private AccessPath(

      @Nullable Element root,

      ImmutableList<AccessPathElement> elements,

  /**

   * Construct the access path of a local.

   *

   * @param node the local

   * @return access path representing the local

   */

  public static AccessPath fromLocal(LocalVariableNode node) {

  }

  /**

   * Construct the access path of a variable declaration.

   *

   * @param node the variable declaration

   * @return access path representing the variable declaration

   */

  static AccessPath fromVarDecl(VariableDeclarationNode node) {

  }

  /**

   * Construct the access path of a field access.

   *

   * @param node the field access

   * @param apContext the current access path context information (see {@link

   *     AccessPath.AccessPathContext}).

   * @return access path for the field access, or <code>null</code> if it cannot be represented

   */

  @Nullable

  static AccessPath fromFieldAccess(FieldAccessNode node, AccessPathContext apContext) {

  }

  @Nullable

  private static AccessPath fromNodeAndContext(Node node, AccessPathContext apContext) {

  }

  /**

   * Construct the access path of a method call.

   *

   * @param node the method call

   * @param apContext the current access path context information (see {@link

   *     AccessPath.AccessPathContext}).

   * @return access path for the method call, or <code>null</code> if it cannot be represented

   */

  @Nullable

  static AccessPath fromMethodCall(

      MethodInvocationNode node, VisitorState state, AccessPathContext apContext) {

    }

  }

  @Nullable

  private static AccessPath fromVanillaMethodCall(

      MethodInvocationNode node, AccessPathContext apContext) {

  }

  /**

   * Returns an access path rooted at {@code newRoot} with the same elements and map-get argument as

   * {@code origAP}

   */

  static AccessPath switchRoot(AccessPath origAP, Element newRoot) {

  }

  /**

   * Construct the access path given a {@code base.element} structure.

   *

   * @param base the base expression for the access path

   * @param element the final element of the access path (a field or method)

   * @param apContext the current access path context information (see {@link

   *     AccessPath.AccessPathContext}).

   * @return the {@link AccessPath} {@code base.element}

   */

  @Nullable

  public static AccessPath fromBaseAndElement(

      Node base, Element element, AccessPathContext apContext) {

  }

  @Nullable

  private static AccessPath fromNodeElementAndContext(

      Node base, AccessPathElement apElement, AccessPathContext apContext) {

  }

  /**

   * Construct the access path given a {@code base.method(CONS)} structure.

   *

   * <p>IMPORTANT: Be careful with this method, the argument list is not the variable names of the

   * method arguments, but rather the string representation of primitive-type compile-time constants

   * or the name of static final fields of structurally immutable types (see {@link

   * #buildAccessPathRecursive(Node, ArrayDeque, AccessPathContext, MapKey)}).

   *

   * <p>This is used by a few specialized Handlers to set nullability around particular paths

   * involving constants.

   *

   * @param base the base expression for the access path

   * @param method the last method call in the access path

   * @param constantArguments a list of <b>constant</b> arguments passed to the method call

   * @param apContext the current access path context information (see {@link

   *     AccessPath.AccessPathContext}).

   * @return the {@link AccessPath} {@code base.method(CONS)}

   */

  @Nullable

  public static AccessPath fromBaseMethodAndConstantArgs(

      Node base, Element method, List<String> constantArguments, AccessPathContext apContext) {

        base, new AccessPathElement(method, constantArguments), apContext);

  }

  /**

   * Construct the access path for <code>map.get(x)</code> from an invocation of <code>put(x)</code>

   * or <code>containsKey(x)</code>.

   *

   * @param node a node invoking containsKey() or put() on a map

   * @param apContext the current access path context information (see {@link

   *     AccessPath.AccessPathContext}).

   * @return an AccessPath representing invoking get() on the same type of map as from node, passing

   *     the same first argument as is passed in node

   */

  @Nullable

  public static AccessPath getForMapInvocation(

      MethodInvocationNode node, VisitorState state, AccessPathContext apContext) {

    // For the receiver type for get, use the declared type of the receiver of the containsKey()

    // call. Note that this may differ from the containing class of the resolved containsKey()

    // method, which can be in a superclass (e.g., LinkedHashMap does not override containsKey())

    // assumption: map type will not both override containsKey() and inherit get()

  }

  private static Node stripCasts(Node node) {

    }

  }

  @Nullable

  private static MapKey argumentToMapKeySpecifier(

      Node argument, VisitorState state, AccessPathContext apContext) {

    // Required to have Node type match Tree type in some instances.

    }

    // A switch at the Tree level should be faster than multiple if checks at the Node level.

      case STRING_LITERAL:

      case INT_LITERAL:

      case LONG_LITERAL:

      case METHOD_INVOCATION:

        // Check for int/long boxing.

        }

        // Fine to fallthrough:

      default:

        // Every other type of expression, including variables, field accesses, new A(...), etc.

    }

  }

  @Nullable

  private static AccessPath fromMapGetCall(

      MethodInvocationNode node, VisitorState state, AccessPathContext apContext) {

    }

  }

  /**

   * Gets corresponding AccessPath for node, if it exists. Handles calls to <code>Map.get()

   * </code>

   *

   * @param node AST node

   * @param state the visitor state

   * @param apContext the current access path context information (see {@link

   *     AccessPath.AccessPathContext}).

   * @return corresponding AccessPath if it exists; <code>null</code> otherwise

   */

  @Nullable

  public static AccessPath getAccessPathForNode(

      Node node, VisitorState state, AccessPathContext apContext) {

    } else {

    }

  }

  /**

   * Constructs an access path ending with the class field element in the argument. The receiver is

   * the method receiver itself.

   *

   * @param element the receiver element.

   * @return access path representing the class field

   */

  public static AccessPath fromFieldElement(VariableElement element) {

  }

  private static boolean isBoxingMethod(Symbol.MethodSymbol methodSymbol) {

    }

  }

  /**

   * A helper function that recursively builds an AccessPath from a CFG node.

   *

   * @param node the CFG node

   * @param elements elements to append to the final access path.

   * @param apContext context information, used to handle cases with constant arguments

   * @param mapKey map key to be used as the map-get argument, or {@code null} if there is no key

   * @return the final access path

   */

  @Nullable

  private static AccessPath buildAccessPathRecursive(

      Node node,

      ArrayDeque<AccessPathElement> elements,

      AccessPathContext apContext,

      @Nullable MapKey mapKey) {

    AccessPath result;

        // this is the root

      } else {

        // instance field access

      }

      AccessPathElement accessPathElement;

          // a zero-argument static method call can be the root of an access path

        } else {

        }

            // Check for boxing call

            }

          }

            case BOOLEAN_LITERAL:

            case CHAR_LITERAL:

            case DOUBLE_LITERAL:

            case FLOAT_LITERAL:

            case INT_LITERAL:

            case LONG_LITERAL:

            case STRING_LITERAL:

            case NULL_LITERAL:

              // Um, probably not? Return null for now.

            case MEMBER_SELECT: // check for Foo.CONST

            case IDENTIFIER: // check for CONST

              // Check for a constant field (static final)

                // From docs: getConstantValue() returns the value of this variable if this is a

                // static final field initialized to a compile-time constant. Returns null

                // otherwise.

                // This means that foo(FOUR) will match foo(4) iff FOUR=4 is a compile time

                // constant :)

                }

                // The above will not work for static final fields of reference type, since they are

                // initialized at class-initialization time, not compile time. Properly handling

                // such fields would further require proving deep immutability for the object type

                // itself. We use a handler-augment list of safe types:

                          + "."

                }

              }

              // Cascade to default, symbol is not a constant field

              // fall through

            default:

          }

      }

          new AccessPath(

    } else {

      // don't handle any other cases

    }

  }

  /**

   * Creates an access path representing a Map get call, where the key is obtained by calling {@code

   * next()} on some {@code Iterator}. Used to support reasoning about iteration over a map's key

   * set using an enhanced-for loop.

   *

   * @param mapNode Node representing the map

   * @param iterVar local variable holding the iterator

   * @param apContext access path context

   * @return access path representing the get call, or {@code null} if the map node cannot be

   *     represented with an access path

   */

  @Nullable

  public static AccessPath mapWithIteratorContentsKey(

      Node mapNode, LocalVariableNode iterVar, AccessPathContext apContext) {

  }

  /**

   * Creates an access path identical to {@code accessPath} (which must represent a map get), but

   * replacing its map {@code get()} argument with {@code mapKey}

   */

  public static AccessPath replaceMapKey(AccessPath accessPath, MapKey mapKey) {

  }

  @Override

  public boolean equals(Object o) {

    }

    }

  }

  @Override

  public int hashCode() {

  }

  /**

   * Returns the root element of the access path. If the root is the receiver argument, returns

   * {@code null}.

   */

  @Nullable

  public Element getRoot() {

  }

  public ImmutableList<AccessPathElement> getElements() {

  }

  @Nullable

  public MapKey getMapGetArg() {

  }

  @Override

  public String toString() {

        + "root="

        + ", elements="

        + elements

        + ", mapGetArg="

        + mapGetArg

        + '}';

  }

  private static boolean isMapGet(Symbol.MethodSymbol symbol, VisitorState state) {

  }

  public static boolean isContainsKey(Symbol.MethodSymbol symbol, VisitorState state) {

  }

  public static boolean isMapPut(Symbol.MethodSymbol symbol, VisitorState state) {

  }

  public static boolean isMapComputeIfAbsent(Symbol.MethodSymbol symbol, VisitorState state) {

  }

  private static final class StringMapKey implements MapKey {

    private final String key;

    @Override

    public int hashCode() {

    }

    @Override

    public boolean equals(Object obj) {

      }

    }

  }

  private static final class NumericMapKey implements MapKey {

    private final long key;

    @Override

    public int hashCode() {

    }

    @Override

    public boolean equals(Object obj) {

      }

    }

  }

  /**

   * Represents all possible values that could be returned by calling {@code next()} on an {@code

   * Iterator} variable

   */

  public static final class IteratorContentsKey implements MapKey {

    /**

     * Element for the local variable holding the {@code Iterator}. We only support locals for now,

     * as this class is designed specifically for reasoning about iterating over map keys using an

     * enhanced-for loop over a {@code keySet()}, and for such cases the iterator is always stored

     * locally

     */

    private final VariableElement iteratorVarElement;

    public VariableElement getIteratorVarElement() {

    }

    @Override

    public boolean equals(Object o) {

      }

      }

    }

    @Override

    public int hashCode() {

    }

  }

  /**

   * Represents a per-javac instance of an AccessPath context options.

   *

   * <p>This includes, for example, data on known structurally immutable types.

   */

  public static final class AccessPathContext {

    private final ImmutableSet<String> immutableTypes;

    public boolean isStructurallyImmutableType(Type type) {

    }

    public static Builder builder() {

    }

    /** class for building up instances of the AccessPathContext. */

    public static final class Builder {

      @Nullable private ImmutableSet<String> immutableTypes;

      /**

       * Passes the set of structurally immutable types registered into this AccessPathContext.

       *

       * <p>See {@link com.uber.nullaway.handlers.Handler#onRegisterImmutableTypes} for more info.

       *

       * @param immutableTypes the immutable types known to our dataflow analysis.

       */

      public Builder setImmutableTypes(ImmutableSet<String> immutableTypes) {

      }

      /**

       * Construct the immutable AccessPathContext instance.

       *

       * @return an access path context constructed from everything added to the builder

       */

      public AccessPathContext build() {

        }

      }

    }

  }

}