content: /*
   * Copyright (C) 2016 The Android Open Source Project
   *
   * 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 art;
  
  import java.io.BufferedReader;
  import java.io.File;
  import java.io.FileReader;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.concurrent.CountDownLatch;
  
  public class Test913 {
    public static void run() throws Exception {
      doTest();
  
      // Use a countdown latch for synchronization, as join() will introduce more roots.
      final CountDownLatch cdl1 = new CountDownLatch(1);
  
      // Run the follow-references tests on a dedicated thread so we know the specific Thread type.
      Thread t = new Thread() {
        @Override
        public void run() {
          try {
            Test913.runFollowReferences();
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
          cdl1.countDown();
        }
      };
      t.start();
      cdl1.await();
  
      doExtensionTests();
    }
  
    public static void runFollowReferences() throws Exception {
      new TestConfig().doFollowReferencesTest();
  
      Runtime.getRuntime().gc();
      Runtime.getRuntime().gc();
  
      new TestConfig(null, 0, 1, -1).doFollowReferencesTest();
  
      Runtime.getRuntime().gc();
      Runtime.getRuntime().gc();
  
      new TestConfig(null, 0, Integer.MAX_VALUE, 1).doFollowReferencesTest();
  
      Runtime.getRuntime().gc();
      Runtime.getRuntime().gc();
  
      doStringTest();
  
      Runtime.getRuntime().gc();
      Runtime.getRuntime().gc();
  
      doPrimitiveArrayTest();
      doPrimitiveFieldTest();
  
      Runtime.getRuntime().gc();
      Runtime.getRuntime().gc();
  
      // Test klass filter.
      System.out.println("--- klass ---");
      new TestConfig(A.class, 0).doFollowReferencesTest();
  
      // Test heap filter.
      System.out.println("--- heap_filter ---");
      System.out.println("---- tagged objects");
      new TestConfig(null, 0x4).doFollowReferencesTest();
      System.out.println("---- untagged objects");
      new TestConfig(null, 0x8).doFollowReferencesTest();
      System.out.println("---- tagged classes");
      new TestConfig(null, 0x10).doFollowReferencesTest();
      System.out.println("---- untagged classes");
      new TestConfig(null, 0x20).doFollowReferencesTest();
    }
  
    public static void doTest() throws Exception {
      setupGcCallback();
  
      enableGcTracking(true);
      runGc();
      enableGcTracking(false);
    }
  
    public static void doStringTest() throws Exception {
      final String str = new String("HelloWorld");
      final String str2 = new String("");
      Object o = new Object() {
        String s = str;
        String s2 = str2;
      };
  
      setTag(str, 1);
      setTag(str2, 2);
      System.out.println(Arrays.toString(followReferencesString(o)));
      System.out.println(getTag(str));
      System.out.println(getTag(str2));
    }
  
    public static void doPrimitiveArrayTest() throws Exception {
      final boolean[] zArray = new boolean[] { false, true };
      setTag(zArray, 1);
  
      final byte[] bArray = new byte[] { 1, 2, 3 };
      setTag(bArray, 2);
  
      final char[] cArray = new char[] { 'A', 'Z' };
      setTag(cArray, 3);
  
      final short[] sArray = new short[] { 1, 2, 3 };
      setTag(sArray, 4);
  
      final int[] iArray = new int[] { 1, 2, 3 };
      setTag(iArray, 5);
  
      final float[] fArray = new float[] { 0.0f, 1.0f };
      setTag(fArray, 6);
  
      final long[] lArray = new long[] { 1, 2, 3 };
      setTag(lArray, 7);
  
      final double[] dArray = new double[] { 0.0, 1.0 };
      setTag(dArray, 8);
  
      Object o = new Object() {
        Object z = zArray;
        Object b = bArray;
        Object c = cArray;
        Object s = sArray;
        Object i = iArray;
        Object f = fArray;
        Object l = lArray;
        Object d = dArray;
      };
  
      System.out.println(followReferencesPrimitiveArray(o));
      System.out.print(getTag(zArray));
      System.out.print(getTag(bArray));
      System.out.print(getTag(cArray));
      System.out.print(getTag(sArray));
      System.out.print(getTag(iArray));
      System.out.print(getTag(fArray));
      System.out.print(getTag(lArray));
      System.out.println(getTag(dArray));
    }
  
    public static void doPrimitiveFieldTest() throws Exception {
      // Force GCs to clean up dirt.
      Runtime.getRuntime().gc();
      Runtime.getRuntime().gc();
  
      doTestPrimitiveFieldsClasses();
  
      doTestPrimitiveFieldsIntegral();
  
      // Force GCs to clean up dirt.
      Runtime.getRuntime().gc();
      Runtime.getRuntime().gc();
  
      doTestPrimitiveFieldsFloat();
  
      // Force GCs to clean up dirt.
      Runtime.getRuntime().gc();
      Runtime.getRuntime().gc();
    }
  
    private static void doTestPrimitiveFieldsClasses() {
      setTag(IntObject.class, 10000);
      System.out.println(followReferencesPrimitiveFields(IntObject.class));
      System.out.println(getTag(IntObject.class));
      setTag(IntObject.class, 0);
  
      setTag(FloatObject.class, 10000);
      System.out.println(followReferencesPrimitiveFields(FloatObject.class));
      System.out.println(getTag(FloatObject.class));
      setTag(FloatObject.class, 0);
  
      setTag(Inf1.class, 10000);
      System.out.println(followReferencesPrimitiveFields(Inf1.class));
      System.out.println(getTag(Inf1.class));
      setTag(Inf1.class, 0);
  
      setTag(Inf2.class, 10000);
      System.out.println(followReferencesPrimitiveFields(Inf2.class));
      System.out.println(getTag(Inf2.class));
      setTag(Inf2.class, 0);
    }
  
    private static void doTestPrimitiveFieldsIntegral() {
      IntObject intObject = new IntObject();
      setTag(intObject, 10000);
      System.out.println(followReferencesPrimitiveFields(intObject));
      System.out.println(getTag(intObject));
    }
  
    private static void doTestPrimitiveFieldsFloat() {
      FloatObject floatObject = new FloatObject();
      setTag(floatObject, 10000);
      System.out.println(followReferencesPrimitiveFields(floatObject));
      System.out.println(getTag(floatObject));
    }
  
    static ArrayList<Object> extensionTestHolder;
  
    private static void doExtensionTests() {
      checkForExtensionApis();
  
      extensionTestHolder = new ArrayList<>();
      System.out.println();
  
      try {
        getHeapName(-1);
        System.out.println("Expected failure for -1");
      } catch (Exception e) {
      }
      System.out.println(getHeapName(0));
      System.out.println(getHeapName(1));
      System.out.println(getHeapName(2));
      System.out.println(getHeapName(3));
      try {
        getHeapName(4);
        System.out.println("Expected failure for -1");
      } catch (Exception e) {
      }
  
      System.out.println();
  
      setTag(Object.class, 100000);
      int objectClassHeapId = getObjectHeapId(100000);
      int objClassExpectedHeapId = hasImage() ? 1 : 3;
      if (objectClassHeapId != objClassExpectedHeapId) {
        throw new RuntimeException("Expected object class in heap " + objClassExpectedHeapId +
            " but received " + objectClassHeapId);
      }
  
      A a = new A();
      extensionTestHolder.add(a);
      setTag(a, 100001);
      System.out.println(getObjectHeapId(100001));
  
      checkGetObjectHeapIdInCallback(100000, objClassExpectedHeapId);
      checkGetObjectHeapIdInCallback(100001, 3);
  
      long baseTag = 30000000;
      setTag(Object.class, baseTag + objClassExpectedHeapId);
      setTag(Class.class, baseTag + objClassExpectedHeapId);
      Object o = new Object();
      extensionTestHolder.add(o);
      setTag(o, baseTag + 3);
  
      iterateThroughHeapExt();
  
      extensionTestHolder = null;
    }
  
    private static void runGc() {
      clearStats();
      forceGarbageCollection();
      printStats();
    }
  
    private static void clearStats() {
      getGcStarts();
      getGcFinishes();
    }
  
    private static void printStats() {
      System.out.println("---");
      int s = getGcStarts();
      int f = getGcFinishes();
      System.out.println((s > 0) + " " + (f > 0));
    }
  
    private static boolean hasImage() {
      try {
        int pid = Integer.parseInt(new File("/proc/self").getCanonicalFile().getName());
        BufferedReader reader = new BufferedReader(new FileReader("/proc/" + pid + "/maps"));
        String line;
        while ((line = reader.readLine()) != null) {
          if (line.endsWith(".art")) {
            reader.close();
            return true;
          }
        }
        reader.close();
        return false;
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
  
    private static class TestConfig {
      private Class<?> klass = null;
      private int heapFilter = 0;
      private int stopAfter = Integer.MAX_VALUE;
      private int followSet = -1;
  
      public TestConfig() {
      }
      public TestConfig(Class<?> klass, int heapFilter) {
        this.klass = klass;
        this.heapFilter = heapFilter;
      }
      public TestConfig(Class<?> klass, int heapFilter, int stopAfter, int followSet) {
        this.klass = klass;
        this.heapFilter = heapFilter;
        this.stopAfter = stopAfter;
        this.followSet = followSet;
      }
  
      public void doFollowReferencesTest() throws Exception {
        // Force GCs to clean up dirt.
        Runtime.getRuntime().gc();
        Runtime.getRuntime().gc();
  
        setTag(Thread.currentThread(), 3000);
  
        {
          ArrayList<Object> tmpStorage = new ArrayList<>();
          doFollowReferencesTestNonRoot(tmpStorage);
          tmpStorage = null;
        }
  
        // Force GCs to clean up dirt.
        Runtime.getRuntime().gc();
        Runtime.getRuntime().gc();
  
        doFollowReferencesTestRoot();
  
        // Force GCs to clean up dirt.
        Runtime.getRuntime().gc();
        Runtime.getRuntime().gc();
      }
  
      private void doFollowReferencesTestNonRoot(ArrayList<Object> tmpStorage) {
        Verifier v = new Verifier();
        tagClasses(v);
        A a = createTree(v);
        tmpStorage.add(a);
        v.add("0@0", "1@1000");  // tmpStorage[0] --(array-element)--> a.
  
        doFollowReferencesTestImpl(null, stopAfter, followSet, null, v, null);
        doFollowReferencesTestImpl(a.foo2, stopAfter, followSet, null, v, "3@1001");
  
        tmpStorage.clear();
      }
  
      private void doFollowReferencesTestRoot() {
        Verifier v = new Verifier();
        tagClasses(v);
        A a = createTree(v);
  
        doFollowReferencesTestImpl(null, stopAfter, followSet, a, v, null);
        doFollowReferencesTestImpl(a.foo2, stopAfter, followSet, a, v, "3@1001");
      }
  
      private void doFollowReferencesTestImpl(A root, int stopAfter, int followSet,
          Object asRoot, Verifier v, String additionalEnabled) {
        String[] lines =
            followReferences(heapFilter, klass, root, stopAfter, followSet, asRoot);
  
        v.process(lines, additionalEnabled, heapFilter != 0 || klass != null);
      }
  
      private static void tagClasses(Verifier v) {
        setTag(A.class, 1000);
  
        setTag(B.class, 1001);
        v.add("1001@0", "1000@0");  // B.class --(superclass)--> A.class.
  
        setTag(C.class, 1002);
        v.add("1002@0", "1001@0");  // C.class --(superclass)--> B.class.
        v.add("1002@0", "2001@0");  // C.class --(interface)--> I2.class.
  
        setTag(I1.class, 2000);
  
        setTag(I2.class, 2001);
        v.add("2001@0", "2000@0");  // I2.class --(interface)--> I1.class.
      }
  
      private static A createTree(Verifier v) {
        A aInst = new A();
        setTag(aInst, 1);
        String aInstStr = "1@1000";
        String aClassStr = "1000@0";
        v.add(aInstStr, aClassStr);  // A -->(class) --> A.class.
  
        A a2Inst = new A();
        setTag(a2Inst, 2);
        aInst.foo = a2Inst;
        String a2InstStr = "2@1000";
        v.add(a2InstStr, aClassStr);  // A2 -->(class) --> A.class.
        v.add(aInstStr, a2InstStr);   // A -->(field) --> A2.
  
        B bInst = new B();
        setTag(bInst, 3);
        aInst.foo2 = bInst;
        String bInstStr = "3@1001";
        String bClassStr = "1001@0";
        v.add(bInstStr, bClassStr);  // B -->(class) --> B.class.
        v.add(aInstStr, bInstStr);   // A -->(field) --> B.
  
        A a3Inst = new A();
        setTag(a3Inst, 4);
        bInst.bar = a3Inst;
        String a3InstStr = "4@1000";
        v.add(a3InstStr, aClassStr);  // A3 -->(class) --> A.class.
        v.add(bInstStr, a3InstStr);   // B -->(field) --> A3.
  
        C cInst = new C();
        setTag(cInst, 5);
        bInst.bar2 = cInst;
        String cInstStr = "5@1000";
        String cClassStr = "1002@0";
        v.add(cInstStr, cClassStr);  // C -->(class) --> C.class.
        v.add(bInstStr, cInstStr);   // B -->(field) --> C.
  
        A a4Inst = new A();
        setTag(a4Inst, 6);
        cInst.baz = a4Inst;
        String a4InstStr = "6@1000";
        v.add(a4InstStr, aClassStr);  // A4 -->(class) --> A.class.
        v.add(cInstStr, a4InstStr);   // C -->(field) --> A4.
  
        cInst.baz2 = aInst;
        v.add(cInstStr, aInstStr);  // C -->(field) --> A.
  
        A[] aArray = new A[2];
        setTag(aArray, 500);
        aArray[1] = a2Inst;
        cInst.array = aArray;
        String aArrayStr = "500@0";
        v.add(cInstStr, aArrayStr);
        v.add(aArrayStr, a2InstStr);
  
        return aInst;
      }
    }
  
    public static class A {
      public A foo;
      public A foo2;
  
      public A() {}
      public A(A a, A b) {
        foo = a;
        foo2 = b;
      }
    }
  
    public static class B extends A {
      public A bar;
      public A bar2;
  
      public B() {}
      public B(A a, A b) {
        bar = a;
        bar2 = b;
      }
    }
  
    public static interface I1 {
      public final static int i1Field = 1;
    }
  
    public static interface I2 extends I1 {
      public final static int i2Field = 2;
    }
  
    public static class C extends B implements I2 {
      public A baz;
      public A baz2;
      public A[] array;
  
      public C() {}
      public C(A a, A b) {
        baz = a;
        baz2 = b;
      }
    }
  
    private static interface Inf1 {
      public final static int A = 1;
    }
  
    private static interface Inf2 extends Inf1 {
      public final static int B = 1;
    }
  
    private static class IntObject implements Inf1 {
      byte b = (byte)1;
      char c= 'a';
      short s = (short)2;
      int i = 3;
      long l = 4;
      Object o = new Object();
      static int sI = 5;
    }
  
    private static class FloatObject extends IntObject implements Inf2 {
      float f = 1.23f;
      double d = 1.23;
      Object p = new Object();
      static int sI = 6;
    }
  
    public static class Verifier {
      // Should roots with vreg=-1 be printed?
      public final static boolean PRINT_ROOTS_WITH_UNKNOWN_VREG = false;
  
      public static class Node {
        public String referrer;
  
        public HashSet<String> referrees = new HashSet<>();
  
        public Node(String r) {
          referrer = r;
        }
  
        public boolean isRoot() {
          return referrer.startsWith("root@");
        }
      }
  
      HashMap<String, Node> nodes = new HashMap<>();
  
      public Verifier() {
      }
  
      public void add(String referrer, String referree) {
        if (!nodes.containsKey(referrer)) {
          nodes.put(referrer, new Node(referrer));
        }
        if (referree != null) {
          nodes.get(referrer).referrees.add(referree);
        }
      }
  
      public void process(String[] lines, String additionalEnabledReferrer, boolean filtered) {
        // This method isn't optimal. The loops could be merged. However, it's more readable if
        // the different parts are separated.
  
        ArrayList<String> rootLines = new ArrayList<>();
        ArrayList<String> nonRootLines = new ArrayList<>();
  
        // Check for consecutive chunks of referrers. Also ensure roots come first.
        {
          String currentHead = null;
          boolean rootsDone = false;
          HashSet<String> completedReferrers = new HashSet<>();
          for (String l : lines) {
            String referrer = getReferrer(l);
  
            if (isRoot(referrer)) {
              if (rootsDone) {
                System.out.println("ERROR: Late root " + l);
                print(lines);
                return;
              }
              rootLines.add(l);
              continue;
            }
  
            rootsDone = true;
  
            if (currentHead == null) {
              currentHead = referrer;
            } else {
              // Ignore 0@0, as it can happen at any time (as it stands for all other objects).
              if (!currentHead.equals(referrer) && !referrer.equals("0@0")) {
                completedReferrers.add(currentHead);
                currentHead = referrer;
                if (completedReferrers.contains(referrer)) {
                  System.out.println("Non-contiguous referrer " + l);
                  print(lines);
                  return;
                }
              }
            }
            nonRootLines.add(l);
          }
        }
  
        // Sort (root order is not specified) and print the roots.
        // TODO: What about extra roots? JNI and the interpreter seem to introduce those (though it
        //       isn't clear why a debuggable-AoT test doesn't have the same, at least for locals).
        //       For now, swallow duplicates, and resolve once we have the metadata for the roots.
        {
          Collections.sort(rootLines);
          String lastRoot = null;
          for (String l : rootLines) {
            if (lastRoot != null && lastRoot.equals(l)) {
              continue;
            }
            lastRoot = l;
            if (!PRINT_ROOTS_WITH_UNKNOWN_VREG && l.indexOf("vreg=-1") > 0) {
              continue;
            }
            System.out.println(l);
          }
        }
  
        if (filtered) {
          // If we aren't tracking dependencies, just sort the lines and print.
          // TODO: As the verifier is currently using the output lines to track dependencies, we
          //       cannot verify that output is correct when parts of it are suppressed by filters.
          //       To correctly track this we need to take node information into account, and
          //       actually analyze the graph.
          Collections.sort(nonRootLines);
          for (String l : nonRootLines) {
            System.out.println(l);
          }
  
          System.out.println("---");
          return;
        }
  
        // Iterate through the lines, keeping track of which referrers are visited, to ensure the
        // order is acceptable.
        HashSet<String> enabled = new HashSet<>();
        if (additionalEnabledReferrer != null) {
          enabled.add(additionalEnabledReferrer);
        }
        // Always add "0@0".
        enabled.add("0@0");
  
        for (String l : lines) {
          String referrer = getReferrer(l);
          String referree = getReferree(l);
          if (isRoot(referrer)) {
            // For a root src, just enable the referree.
            enabled.add(referree);
          } else {
            // Check that the referrer is enabled (may be visited).
            if (!enabled.contains(referrer)) {
              System.out.println("Referrer " + referrer + " not enabled: " + l);
              print(lines);
              return;
            }
            enabled.add(referree);
          }
        }
  
        // Now just sort the non-root lines and output them
        Collections.sort(nonRootLines);
        for (String l : nonRootLines) {
          System.out.println(l);
        }
  
        System.out.println("---");
      }
  
      public static boolean isRoot(String ref) {
        return ref.startsWith("root@");
      }
  
      private static String getReferrer(String line) {
        int i = line.indexOf(" --");
        if (i <= 0) {
          throw new IllegalArgumentException(line);
        }
        int j = line.indexOf(' ');
        if (i != j) {
          throw new IllegalArgumentException(line);
        }
        return line.substring(0, i);
      }
  
      private static String getReferree(String line) {
        int i = line.indexOf("--> ");
        if (i <= 0) {
          throw new IllegalArgumentException(line);
        }
        int j = line.indexOf(' ', i + 4);
        if (j < 0) {
          throw new IllegalArgumentException(line);
        }
        return line.substring(i + 4, j);
      }
  
      private static void print(String[] lines) {
        for (String l : lines) {
          System.out.println(l);
        }
      }
    }
  
    private static void setTag(Object o, long tag) {
      Main.setTag(o, tag);
    }
    private static long getTag(Object o) {
      return Main.getTag(o);
    }
  
    private static native void setupGcCallback();
    private static native void enableGcTracking(boolean enable);
    private static native int getGcStarts();
    private static native int getGcFinishes();
    private static native void forceGarbageCollection();
  
    private static native void checkForExtensionApis();
    private static native int getObjectHeapId(long tag);
    private static native String getHeapName(int heapId);
    private static native void checkGetObjectHeapIdInCallback(long tag, int heapId);
  
    public static native String[] followReferences(int heapFilter, Class<?> klassFilter,
        Object initialObject, int stopAfter, int followSet, Object jniRef);
    public static native String[] followReferencesString(Object initialObject);
    public static native String followReferencesPrimitiveArray(Object initialObject);
    public static native String followReferencesPrimitiveFields(Object initialObject);
  
    private static native void iterateThroughHeapExt();
  }
  