/*
 * 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);

        boolean correctHeapValue = false;
        setTag(Inf1.class, 10000);
        String heapTrace = followReferencesPrimitiveFields(Inf1.class);

        if (!checkInitialized(Inf1.class)) {
            correctHeapValue = heapTrace.equals("10000@0 (static, int, index=0) 0000000000000000");
        } else {
            correctHeapValue = heapTrace.equals("10000@0 (static, int, index=0) 0000000000000001");
        }

        if (!correctHeapValue) {
            System.out.println("Heap Trace for Inf1 is not as expected:\n" + heapTrace);
        }

        System.out.println(getTag(Inf1.class));
        setTag(Inf1.class, 0);

        setTag(Inf2.class, 10000);
        heapTrace = followReferencesPrimitiveFields(Inf2.class);

        if (!checkInitialized(Inf2.class)) {
            correctHeapValue = heapTrace.equals("10000@0 (static, int, index=1) 0000000000000000");
        } else {
            correctHeapValue = heapTrace.equals("10000@0 (static, int, index=1) 0000000000000001");
        }

        if (!correctHeapValue)
            System.out.println("Heap Trace for Inf2 is not as expected:\n" + heapTrace);
        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) {
                // On host the mappings end with .art and on device they end with .art]
                if (line.endsWith(".art]") || 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);
            registerClass(1000, A.class);

            setTag(B.class, 1001);
            registerClass(1001, B.class);
            v.add("1001@0", "1000@0");  // B.class --(superclass)--> A.class.

            setTag(C.class, 1002);
            registerClass(1002, C.class);
            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);
            registerClass(2000, I1.class);

            setTag(I2.class, 2001);
            registerClass(2001, I2.class);
            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 boolean checkInitialized(Class<?> klass);
    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();

    private static native void registerClass(long tag, Object obj);
}