/*
 * Copyright (C) 2017 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.
 */

import java.lang.Thread.State;
import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.ForkJoinPool;

public class Main {

    static class Runner implements Runnable {
        List<Object> locks;
        List<CyclicBarrier> barriers;

        public Runner(List<Object> locks, List<CyclicBarrier> barriers) {
            this.locks = locks;
            this.barriers = barriers;
        }

        @Override
        public void run() {
            step(locks, barriers);
        }

        private void step(List<Object> l, List<CyclicBarrier> b) {
            if (l.isEmpty()) {
                // Nothing to do, sleep indefinitely.
                try {
                    Thread.sleep(100000000);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            } else {
                Object lockObject = l.remove(0);
                CyclicBarrier barrierObject = b.remove(0);

                if (lockObject == null) {
                    // No lock object: only take barrier, recurse.
                    try {
                        barrierObject.await();
                    } catch (InterruptedException | BrokenBarrierException e) {
                        throw new RuntimeException(e);
                    }
                    step(l, b);
                } else if (barrierObject != null) {
                    // Have barrier: sync, wait and recurse.
                    synchronized(lockObject) {
                        try {
                            barrierObject.await();
                        } catch (InterruptedException | BrokenBarrierException e) {
                            throw new RuntimeException(e);
                        }
                        step(l, b);
                    }
                } else {
                    // Sync, and get next step (which is assumed to have object and barrier).
                    synchronized (lockObject) {
                        Object lockObject2 = l.remove(0);
                        CyclicBarrier barrierObject2 = b.remove(0);
                        synchronized(lockObject2) {
                            try {
                                barrierObject2.await();
                            } catch (InterruptedException | BrokenBarrierException e) {
                                throw new RuntimeException(e);
                            }
                            step(l, b);
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        // Eagerly initialize ForkJoinPool as we've seen the class initialization code interfere
        // with the logic of the test when waiting for threads to be non-runnable.
        Class.forName(ForkJoinPool.class.getName(), true, ForkJoinPool.class.getClassLoader());
        try {
            testCluster1();
        } catch (Exception e) {
            Map<Thread,StackTraceElement[]> stacks = Thread.getAllStackTraces();
            for (Map.Entry<Thread,StackTraceElement[]> entry : stacks.entrySet()) {
                System.out.println(entry.getKey());
                System.out.println(Arrays.toString(entry.getValue()));
            }
            throw e;
        }
    }

    private static void testCluster1() throws Exception {
        // Test setup (at deadlock):
        //
        // Thread 1:
        //   #0 step: synchornized(o3) { synchronized(o2) }
        //   #1 step: synchronized(o1)
        //
        // Thread 2:
        //   #0 step: synchronized(o1)
        //   #1 step: synchronized(o4) { synchronized(o2) }
        //
        LinkedList<Object> l1 = new LinkedList<>();
        LinkedList<CyclicBarrier> b1 = new LinkedList<>();
        LinkedList<Object> l2 = new LinkedList<>();
        LinkedList<CyclicBarrier> b2 = new LinkedList<>();

        Object o1 = new Object();
        Object o2 = new Object();
        Object o3 = new Object();
        Object o4 = new Object();

        l1.add(o1);
        l1.add(o3);
        l1.add(o2);
        l2.add(o4);
        l2.add(o2);
        l2.add(o1);

        CyclicBarrier c1 = new CyclicBarrier(3);
        CyclicBarrier c2 = new CyclicBarrier(2);
        b1.add(c1);
        b1.add(null);
        b1.add(c2);
        b2.add(null);
        b2.add(c1);
        b2.add(c2);

        Thread t1 = new Thread(new Runner(l1, b1));
        t1.setDaemon(true);
        t1.start();
        Thread t2 = new Thread(new Runner(l2, b2));
        t2.setDaemon(true);
        t2.start();

        c1.await();

        waitNotRunnable(t1);
        waitNotRunnable(t2);
        Thread.sleep(250);    // Unfortunately this seems necessary. :-(

        // Thread 1.
        {
            Object[] stack1 = getAnnotatedStack(t1);
            assertBlockedOn(stack1[0], o2);              // Blocked on o2.
            assertLocks(stack1[0], o3);                  // Locked o3.
            assertStackTraceElementStep(stack1[0]);

            assertBlockedOn(stack1[1], null);            // Frame can't be blocked.
            assertLocks(stack1[1], o1);                  // Locked o1.
            assertStackTraceElementStep(stack1[1]);
        }

        // Thread 2.
        {
            Object[] stack2 = getAnnotatedStack(t2);
            assertBlockedOn(stack2[0], o1);              // Blocked on o1.
            assertLocks(stack2[0]);                      // Nothing locked.
            assertStackTraceElementStep(stack2[0]);

            assertBlockedOn(stack2[1], null);            // Frame can't be blocked.
            assertLocks(stack2[1], o4, o2);              // Locked o4, o2.
            assertStackTraceElementStep(stack2[1]);
        }
    }

    private static void waitNotRunnable(Thread t) throws InterruptedException {
        while (t.getState() == State.RUNNABLE) {
            Thread.sleep(100);
        }
    }

    private static Object[] getAnnotatedStack(Thread t) throws Exception {
        Class<?> vmStack = Class.forName("dalvik.system.VMStack");
        Method m = vmStack.getDeclaredMethod("getAnnotatedThreadStackTrace", Thread.class);
        return (Object[]) m.invoke(null, t);
    }

    private static void assertEquals(Object o1, Object o2) {
        if (o1 != o2) {
            throw new RuntimeException("Expected " + o1 + " == " + o2);
        }
    }
    private static void assertLocks(Object fromTrace, Object... locks) throws Exception {
        Object fieldValue = fromTrace.getClass().getDeclaredMethod("getHeldLocks").
                invoke(fromTrace);
        assertEquals((Object[]) fieldValue,
                (locks == null) ? null : (locks.length == 0 ? null : locks));
    }
    private static void assertBlockedOn(Object fromTrace, Object block) throws Exception {
        Object fieldValue = fromTrace.getClass().getDeclaredMethod("getBlockedOn").
                invoke(fromTrace);
        assertEquals(fieldValue, block);
    }
    private static void assertEquals(Object[] o1, Object[] o2) {
        if (!Arrays.equals(o1, o2)) {
            throw new RuntimeException(
                    "Expected " + Arrays.toString(o1) + " == " + Arrays.toString(o2));
        }
    }
    private static void assertStackTraceElementStep(Object o) throws Exception {
        Object fieldValue = o.getClass().getDeclaredMethod("getStackTraceElement").invoke(o);
        if (fieldValue instanceof StackTraceElement) {
            StackTraceElement elem = (StackTraceElement) fieldValue;
            if (!elem.getMethodName().equals("step")) {
                throw new RuntimeException("Expected step method");
            }
            return;
        }
        throw new RuntimeException("Expected StackTraceElement " + fieldValue + " / " + o);
    }
}