// Copyright (c) 2018, 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.utils.codeinspector;

import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.naming.MemberNaming.MethodSignature;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

// This class is used to check that all non-abstract classes in an application implement the
// abstract/interface methods from their super types. This is used as a sanity check for
// minification.
public class ClassHierarchyVerifier {

  private final boolean allowDefaultInterfaceMethods;
  private final ClassHierarchy hierarchy;
  private final CodeInspector inspector;

  // State of the traversal.
  private final Deque<DexType> path = new ArrayDeque<>();
  private final Set<DexType> visited = Sets.newIdentityHashSet();

  public ClassHierarchyVerifier(CodeInspector inspector) {
    this(inspector, true);
  }

  public ClassHierarchyVerifier(CodeInspector inspector, boolean allowDefaultInterfaceMethods) {
    this.allowDefaultInterfaceMethods = allowDefaultInterfaceMethods;
    this.hierarchy = ClassHierarchy.build(inspector);
    this.inspector = inspector;
  }

  public void run() {
    try {
      // Top-down traversal of the class hierarchy starting from all the roots.
      for (FoundClassSubject classSubject : hierarchy.getRoots()) {
        visitType(classSubject, ImmutableSet.of());
      }
    } finally {
      path.clear();
      visited.clear();
    }
  }

  private void visitType(
      FoundClassSubject classSubject, ImmutableSet<DexMethod> unimplementedInSupertype) {
    DexClass clazz = classSubject.getDexClass();
    DexType type = clazz.type;

    ImmutableSet.Builder<DexMethod> unimplementedInCurrentTypeBuilder = ImmutableSet.builder();
    if (clazz.accessFlags.isAbstract() || clazz.accessFlags.isInterface()) {
      // Collected methods that are still not implemented. This step needs to be repeated although
      // the type has been visited previously because we are coming from another path where the
      // set of unimplemented methods are (potentially) different.
      for (DexMethod method : unimplementedInSupertype) {
        if (clazz.lookupVirtualMethod(method) == null) {
          unimplementedInCurrentTypeBuilder.add(method);
        }
      }
      // Add methods that do not have an implementation. If this type has been visited previously,
      // then we have already checked that all subtypes implement these methods, and therefore we
      // do not have to add them to the set of unimplemented methods.
      if (!visited.contains(type)) {
        for (DexEncodedMethod method : clazz.virtualMethods()) {
          if (method.accessFlags.isAbstract()) {
            unimplementedInCurrentTypeBuilder.add(method.method);
          } else {
            assert allowDefaultInterfaceMethods || !clazz.accessFlags.isInterface();
          }
        }
      }
    } else {
      // Check that there are no unimplemented methods. This step needs to be repeated although the
      // type has been visited previously because we are coming from another path where the
      // set of unimplemented methods are (potentially) different.
      for (DexMethod method : unimplementedInSupertype) {
        if (clazz.lookupVirtualMethod(method) == null) {
          fail(classSubject, method);
        }
      }
      // Check that all methods have an implementation. This step can be skipped if the type has
      // already been visited previously.
      if (!visited.contains(type)) {
        for (DexEncodedMethod method : clazz.virtualMethods()) {
          if (method.accessFlags.isAbstract()) {
            fail(classSubject, method.method);
          }
        }
      }
    }

    path.push(type);
    visited.add(type);

    // Continue traversal downwards.
    ImmutableSet<DexMethod> unimplementedInCurrentType = unimplementedInCurrentTypeBuilder.build();
    for (FoundClassSubject subClassSubject : hierarchy.getDirectSubtypes(classSubject)) {
      visitType(subClassSubject, unimplementedInCurrentType);
    }

    DexType popped = path.pop();
    assert popped == type;
  }

  private void fail(ClassSubject classSubject, DexMethod method) {
    StringBuilder builder = new StringBuilder();
    builder.append("Non-abstract class ").append(classSubject.getFinalName());
    builder.append(" must implement method '").append(method.toSourceString()).append("'");

    if (classSubject.isRenamed()) {
      builder.append(" (original: ").append(classSubject.getOriginalName()).append(")");
    }

    Iterator<DexType> superTypeIterator = path.descendingIterator();
    if (superTypeIterator.hasNext()) {
      builder.append(", super types:");
      while (superTypeIterator.hasNext()) {
        DexType superType = superTypeIterator.next();
        ClassSubject superClassSubject = inspector.clazz(superType.toSourceString());
        assert superClassSubject.isPresent();

        builder.append(System.lineSeparator()).append(" - ");
        builder.append(superClassSubject.getFinalName());

        List<String> attributes = new ArrayList<>();
        if (superClassSubject.isRenamed()) {
          attributes.add("original: " + superClassSubject.getOriginalName());
        }
        MethodSubject methodSubject =
            superClassSubject.method(MethodSignature.fromDexMethod(method));
        if (methodSubject.isPresent()) {
          attributes.add("method: " + methodSubject.getOriginalSignature());
        }
        builder.append(" (").append(String.join(", ", attributes)).append(")");
      }
    } else {
      builder.append(", super types: none");
    }
    throw new AssertionError(builder.toString());
  }
}