src/main/java/com/android/tools/r8/shaking/ProguardTypeMatcher.java

// Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.shaking;

import static com.android.tools.r8.utils.DescriptorUtils.javaTypeToDescriptor;

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.shaking.ProguardConfigurationParser.IdentifierPatternWithWildcards;
import com.android.tools.r8.shaking.ProguardWildcard.BackReference;
import com.android.tools.r8.shaking.ProguardWildcard.Pattern;
import com.android.tools.r8.utils.DescriptorUtils;
import com.android.tools.r8.utils.StringUtils;
import com.google.common.collect.ImmutableList;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public abstract class ProguardTypeMatcher {

  private static final String MATCH_ALL_PATTERN = "***";
  private static final String MATCH_ANY_ARG_SEQUENCE_PATTERN = "...";
  private static final String LEGACY_MATCH_CLASS_PATTERN = "*";
  private static final String MATCH_CLASS_PATTERN = "**";
  private static final String MATCH_BASIC_PATTERN = "%";

  private ProguardTypeMatcher() {
  }

  enum ClassOrType {
    CLASS,
    TYPE
  }

  public MatchSpecificType asSpecificTypeMatcher() {
    return null;
  }

  // Evaluates this matcher on the given type.
  public abstract boolean matches(DexType type);

  // Evaluates this matcher on the given type, and on all types that have been merged into the given
  // type, if any.
  public final boolean matches(DexType type, AppView<?> appView) {
    if (matches(type)) {
      return true;
    }
    if (appView.verticallyMergedClasses() != null) {
      return appView.verticallyMergedClasses().getSourcesFor(type).stream().anyMatch(this::matches);
    }
    return false;
  }

  protected Iterable<ProguardWildcard> getWildcards() {
    return Collections::emptyIterator;
  }

  static Iterable<ProguardWildcard> getWildcardsOrEmpty(ProguardTypeMatcher typeMatcher) {
    return typeMatcher == null ? Collections::emptyIterator : typeMatcher.getWildcards();
  }

  static Iterable<ProguardWildcard> getWildcardsOrEmpty(List<ProguardTypeMatcher> typeMatchers) {
    List<ProguardWildcard> result = new ArrayList<>();
    for (ProguardTypeMatcher typeMatcher : typeMatchers) {
      typeMatcher.getWildcards().forEach(result::add);
    }
    return result;
  }

  protected ProguardTypeMatcher materialize(DexItemFactory dexItemFactory) {
    return this;
  }

  public static List<ProguardTypeMatcher> materializeList(
      List<ProguardTypeMatcher> matchers, DexItemFactory dexItemFactory) {
    if (matchers.isEmpty()) {
      return Collections.emptyList();
    }
    ImmutableList.Builder<ProguardTypeMatcher> builder = ImmutableList.builder();
    for (ProguardTypeMatcher matcher : matchers) {
      builder.add(matcher.materialize(dexItemFactory));
    }
    return builder.build();
  }

  @Override
  public abstract String toString();

  public boolean isTripleDotPattern() {
    return false;
  }

  public static ProguardTypeMatcher create(
      IdentifierPatternWithWildcards identifierPatternWithWildcards,
      ClassOrType kind,
      DexItemFactory dexItemFactory) {
    if (identifierPatternWithWildcards == null || identifierPatternWithWildcards.pattern == null) {
      return null;
    }
    switch (identifierPatternWithWildcards.pattern) {
      case MATCH_ALL_PATTERN:
        return MatchAllTypes.MATCH_ALL_TYPES;
      case MATCH_ANY_ARG_SEQUENCE_PATTERN:
        return MatchAnyArgSequence.MATCH_ANY_ARG_SEQUENCE;
      case MATCH_CLASS_PATTERN:
        return MatchClassTypes.MATCH_CLASS_TYPES;
      case LEGACY_MATCH_CLASS_PATTERN:
        return MatchClassTypes.LEGACY_MATCH_CLASS_TYPES;
      case MATCH_BASIC_PATTERN:
        return MatchBasicTypes.MATCH_BASIC_TYPES;
      default:
        if (identifierPatternWithWildcards.wildcards.isEmpty()) {
          return new MatchSpecificType(dexItemFactory.createType(
              javaTypeToDescriptor(identifierPatternWithWildcards.pattern)));
        }
        return new MatchTypePattern(identifierPatternWithWildcards, kind);
    }
  }

  public static ProguardTypeMatcher create(DexType type) {
    return new MatchSpecificType(type);
  }

  public static ProguardTypeMatcher defaultAllMatcher() {
    return MatchAllTypes.MATCH_ALL_TYPES;
  }

  @Override
  public abstract boolean equals(Object o);

  @Override
  public abstract int hashCode();

  public boolean hasSpecificType() {
    return false;
  }

  public DexType getSpecificType() {
    return null;
  }

  public final boolean matchesSpecificType() {
    return getSpecificType() != null;
  }

  private static class MatchAllTypes extends ProguardTypeMatcher {

    private static final ProguardTypeMatcher MATCH_ALL_TYPES = new MatchAllTypes();

    private final ProguardWildcard wildcard;

    MatchAllTypes() {
      this(new Pattern(MATCH_ALL_PATTERN));
    }

    private MatchAllTypes(ProguardWildcard wildcard) {
      this.wildcard = wildcard;
    }

    @Override
    public boolean matches(DexType type) {
      wildcard.setCaptured(type.toSourceString());
      return true;
    }

    @Override
    protected Iterable<ProguardWildcard> getWildcards() {
      return ImmutableList.of(wildcard);
    }

    @Override
    protected MatchAllTypes materialize(DexItemFactory dexItemFactory) {
      return new MatchAllTypes(wildcard.materialize());
    }

    @Override
    public String toString() {
      return MATCH_ALL_PATTERN;
    }

    @Override
    public boolean equals(Object o) {
      return o instanceof MatchAllTypes;
    }

    @Override
    public int hashCode() {
      return getClass().hashCode();
    }
  }

  private static class MatchAnyArgSequence extends ProguardTypeMatcher {

    private static final ProguardTypeMatcher MATCH_ANY_ARG_SEQUENCE = new MatchAnyArgSequence();

    @Override
    public boolean matches(DexType type) {
      return true;
    }

    @Override
    public String toString() {
      return MATCH_ANY_ARG_SEQUENCE_PATTERN;
    }

    @Override
    public boolean isTripleDotPattern() {
      return true;
    }

    @Override
    public boolean equals(Object o) {
      return o instanceof MatchAnyArgSequence;
    }

    @Override
    public int hashCode() {
      return getClass().hashCode();
    }
  }

  private static class MatchClassTypes extends ProguardTypeMatcher {

    private static final ProguardTypeMatcher MATCH_CLASS_TYPES =
        new MatchClassTypes(MATCH_CLASS_PATTERN);
    private static final ProguardTypeMatcher LEGACY_MATCH_CLASS_TYPES =
        new MatchClassTypes(LEGACY_MATCH_CLASS_PATTERN);

    private final String pattern;
    private final ProguardWildcard wildcard;

    private MatchClassTypes(String pattern) {
      this(pattern, new Pattern(pattern));
    }

    private MatchClassTypes(String pattern, ProguardWildcard wildcard) {
      assert pattern.equals(LEGACY_MATCH_CLASS_PATTERN) || pattern.equals(MATCH_CLASS_PATTERN);
      this.pattern = pattern;
      this.wildcard = wildcard;
    }

    @Override
    public boolean matches(DexType type) {
      if (type.isClassType()) {
        wildcard.setCaptured(type.toSourceString());
        return true;
      }
      return false;
    }

    @Override
    protected Iterable<ProguardWildcard> getWildcards() {
      return ImmutableList.of(wildcard);
    }

    @Override
    protected MatchClassTypes materialize(DexItemFactory dexItemFactory) {
      return new MatchClassTypes(pattern, wildcard.materialize());
    }

    @Override
    public String toString() {
      return pattern;
    }

    @Override
    public boolean equals(Object o) {
      return o instanceof MatchClassTypes && pattern.equals(((MatchClassTypes) o).pattern);
    }

    @Override
    public int hashCode() {
      return pattern.hashCode();
    }
  }

  private static class MatchBasicTypes extends ProguardTypeMatcher {

    private static final ProguardTypeMatcher MATCH_BASIC_TYPES = new MatchBasicTypes();

    private final ProguardWildcard wildcard;

    MatchBasicTypes() {
      this(new Pattern(MATCH_BASIC_PATTERN));
    }

    private MatchBasicTypes(ProguardWildcard wildcard) {
      this.wildcard = wildcard;
    }

    @Override
    public boolean matches(DexType type) {
      if (type.isPrimitiveType()) {
        wildcard.setCaptured(type.toSourceString());
        return true;
      }
      return false;
    }

    @Override
    protected Iterable<ProguardWildcard> getWildcards() {
      return ImmutableList.of(wildcard);
    }

    @Override
    protected MatchBasicTypes materialize(DexItemFactory dexItemFactory) {
      return new MatchBasicTypes(wildcard.materialize());
    }

    @Override
    public String toString() {
      return MATCH_BASIC_PATTERN;
    }

    @Override
    public boolean equals(Object o) {
      return o instanceof MatchBasicTypes;
    }

    @Override
    public int hashCode() {
      return getClass().hashCode();
    }
  }

  public static class MatchSpecificType extends ProguardTypeMatcher {

    public final DexType type;

    private MatchSpecificType(DexType type) {
      this.type = type;
    }

    @Override
    public MatchSpecificType asSpecificTypeMatcher() {
      return this;
    }

    @Override
    public boolean matches(DexType type) {
      return this.type == type;
    }

    @Override
    public String toString() {
      return type.toSourceString();
    }

    @Override
    public boolean equals(Object o) {
      if (o instanceof MatchSpecificType) {
        return type.equals(((MatchSpecificType) o).type);
      }
      return false;
    }

    @Override
    public int hashCode() {
      return type.hashCode();
    }

    @Override
    public boolean hasSpecificType() {
      return true;
    }

    @Override
    public DexType getSpecificType() {
      return type;
    }
  }

  private static class MatchTypePattern extends ProguardTypeMatcher {

    private final String pattern;
    private final List<ProguardWildcard> wildcards;
    private final ClassOrType kind;

    private MatchTypePattern(
        IdentifierPatternWithWildcards identifierPatternWithWildcards, ClassOrType kind) {
      this.pattern = identifierPatternWithWildcards.pattern;
      this.wildcards = identifierPatternWithWildcards.wildcards;
      this.kind = kind;
    }

    @Override
    public boolean matches(DexType type) {
      // TODO(herhut): Translate pattern to work on descriptors instead.
      String typeName = type.toSourceString();
      boolean matched = matchClassOrTypeNameImpl(pattern, 0, typeName, 0, wildcards, 0, kind);
      if (!matched) {
        wildcards.forEach(ProguardWildcard::clearCaptured);
      }
      return matched;
    }

    @Override
    protected Iterable<ProguardWildcard> getWildcards() {
      return wildcards;
    }

    @Override
    protected ProguardTypeMatcher materialize(DexItemFactory dexItemFactory) {
      Int2ReferenceMap<String> materializedBackReferences = new Int2ReferenceOpenHashMap<>();
      List<ProguardWildcard> materializedWildcards = new ArrayList<>();
      for (ProguardWildcard wildcard : wildcards) {
        ProguardWildcard materializedWildcard = wildcard.materialize();
        if (materializedWildcard.isBackReference()) {
          BackReference materializedBackReference = materializedWildcard.asBackReference();
          materializedBackReferences.put(
              materializedBackReference.referenceIndex, materializedBackReference.getCaptured());
        } else {
          materializedWildcards.add(materializedWildcard);
        }
      }

      if (!materializedBackReferences.isEmpty()) {
        String newPattern =
            removeMaterializedBackReferencesFromPattern(pattern, materializedBackReferences);
        if (!newPattern.contains("*")) {
          String descriptor = DescriptorUtils.javaTypeToDescriptor(newPattern);
          DexType type = dexItemFactory.createType(descriptor);
          return new MatchSpecificType(type);
        }

        IdentifierPatternWithWildcards identifierPatternWithMaterializedWildcards =
            new IdentifierPatternWithWildcards(newPattern, materializedWildcards);
        return new MatchTypePattern(identifierPatternWithMaterializedWildcards, kind);
      }

      IdentifierPatternWithWildcards identifierPatternWithMaterializedWildcards =
          new IdentifierPatternWithWildcards(pattern, materializedWildcards);
      return new MatchTypePattern(identifierPatternWithMaterializedWildcards, kind);
    }

    private static String removeMaterializedBackReferencesFromPattern(
        String pattern, Int2ReferenceMap<String> materializedBackReferences) {
      StringBuilder builder = new StringBuilder();
      int startIndex = 0;
      int currentIndex = 0;
      for (; currentIndex < pattern.length(); currentIndex++) {
        char c = pattern.charAt(currentIndex);
        if (c == '<') {
          int backReferenceEndIndex = currentIndex + 1;
          while (backReferenceEndIndex < pattern.length()
              && pattern.charAt(backReferenceEndIndex) != '>') {
            backReferenceEndIndex++;
          }
          if (backReferenceEndIndex == pattern.length()) {
            // Reached the end of the string without finding '>'.
            break;
          }

          String reference = pattern.substring(currentIndex + 1, backReferenceEndIndex);
          if (reference.isEmpty() || !StringUtils.onlyContainsDigits(reference)) {
            continue;
          }

          String captured = materializedBackReferences.get(Integer.valueOf(reference).intValue());
          if (captured == null) {
            continue;
          }

          // Flush everything up until the back reference.
          String before = pattern.substring(startIndex, currentIndex);
          builder.append(before);

          // Output the captured value.
          builder.append(captured);

          // Continue from the character that follows '>'.
          startIndex = backReferenceEndIndex + 1;
          currentIndex = backReferenceEndIndex;
        }
      }

      assert currentIndex == pattern.length();

      // Output everything that follows the last back reference.
      if (startIndex < currentIndex) {
        builder.append(pattern.substring(startIndex));
      }

      return builder.toString();
    }

    private static boolean matchClassOrTypeNameImpl(
        String pattern, int patternIndex,
        String name, int nameIndex,
        List<ProguardWildcard> wildcards, int wildcardIndex,
        ClassOrType kind) {
      ProguardWildcard wildcard;
      Pattern wildcardPattern;
      BackReference backReference;
      for (int i = patternIndex; i < pattern.length(); i++) {
        char patternChar = pattern.charAt(i);
        switch (patternChar) {
          case '*':
            wildcard = wildcards.get(wildcardIndex);
            assert wildcard.isPattern();
            wildcardPattern = wildcard.asPattern();

            boolean includeSeparators = pattern.length() > (i + 1) && pattern.charAt(i + 1) == '*';
            boolean includeAll =
                includeSeparators && pattern.length() > (i + 2) && pattern.charAt(i + 2) == '*';
            int nextPatternIndex = i + 1;
            if (includeAll) {
              nextPatternIndex += 2;
            } else if (includeSeparators) {
              nextPatternIndex += 1;
            }

            // Fast cases for the common case where a pattern ends with  '*', '**', or '***'.
            if (nextPatternIndex == pattern.length()) {
              wildcardPattern.setCaptured(name.substring(nameIndex));
              if (includeAll) {
                return true;
              }
              if (includeSeparators) {
                return kind == ClassOrType.CLASS || !isArrayType(name);
              }
              boolean hasSeparators = containsSeparatorsStartingAt(name, nameIndex);
              return !hasSeparators && (kind == ClassOrType.CLASS || !isArrayType(name));
            }

            // Match the rest of the pattern against the (non-empty) rest of the class name.
            for (int nextNameIndex = nameIndex; nextNameIndex < name.length(); nextNameIndex++) {
              wildcardPattern.setCaptured(name.substring(nameIndex, nextNameIndex));
              if (!includeSeparators) {
                if (name.charAt(nextNameIndex) == '.') {
                  return matchClassOrTypeNameImpl(
                      pattern,
                      nextPatternIndex,
                      name,
                      nextNameIndex,
                      wildcards,
                      wildcardIndex + 1,
                      kind);
                }
              }
              if (kind == ClassOrType.TYPE && name.charAt(nextNameIndex) == '[') {
                return matchClassOrTypeNameImpl(
                    pattern, nextPatternIndex, name, nextNameIndex, wildcards, wildcardIndex + 1,
                    kind);
              }
              if (matchClassOrTypeNameImpl(
                  pattern, nextPatternIndex, name, nextNameIndex, wildcards, wildcardIndex + 1,
                  kind)) {
                return true;
              }
            }

            // Finally, check the case where the '*', '**', or '***' eats all of the class name.
            wildcardPattern.setCaptured(name.substring(nameIndex));
            return matchClassOrTypeNameImpl(
                pattern, nextPatternIndex, name, name.length(), wildcards, wildcardIndex + 1, kind);

          case '?':
            wildcard = wildcards.get(wildcardIndex);
            assert wildcard.isPattern();
            if (nameIndex == name.length() || name.charAt(nameIndex) == '.') {
              return false;
            }
            wildcardPattern = wildcard.asPattern();
            wildcardPattern.setCaptured(name.substring(nameIndex, nameIndex + 1));
            nameIndex++;
            wildcardIndex++;
            break;

          case '<':
            wildcard = wildcards.get(wildcardIndex);
            assert wildcard.isBackReference();
            backReference = wildcard.asBackReference();
            String captured = backReference.getCaptured();
            if (captured == null
                || name.length() < nameIndex + captured.length()
                || !captured.equals(name.substring(nameIndex, nameIndex + captured.length()))) {
              return false;
            }
            nameIndex = nameIndex + captured.length();
            wildcardIndex++;
            i = pattern.indexOf(">", i);
            break;

          default:
            if (nameIndex == name.length() || patternChar != name.charAt(nameIndex++)) {
              return false;
            }
            break;
        }
      }
      return nameIndex == name.length();
    }

    private static boolean containsSeparatorsStartingAt(String className, int nameIndex) {
      return className.indexOf('.', nameIndex) != -1;
    }

    private static boolean isArrayType(String type) {
      int length = type.length();
      if (length < 2) {
        return false;
      }
      return type.charAt(length - 1) == ']' && type.charAt(length - 2) == '[';
    }

    @Override
    public String toString() {
      return pattern;
    }

    @Override
    public boolean equals(Object o) {
      if (o instanceof MatchTypePattern) {
        MatchTypePattern that = (MatchTypePattern) o;
        return kind.equals(that.kind) && pattern.equals(that.pattern);
      }
      return false;
    }

    @Override
    public int hashCode() {
      return pattern.hashCode() * 7 + kind.hashCode();
    }
  }
}