/*

 * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package java.lang;

import sun.misc.VM;

import java.io.PrintStream;

import java.lang.StackWalker.Option;

import java.lang.StackWalker.StackFrame;

import java.lang.annotation.Native;

import java.lang.reflect.Method;

import java.security.AccessController;

import java.security.PrivilegedAction;

import java.util.Arrays;

import java.util.EnumSet;

import java.util.HashSet;

import java.util.NoSuchElementException;

import java.util.Objects;

import java.util.Optional;

import java.util.Set;

import java.util.Spliterator;

import java.util.function.Consumer;

import java.util.function.Function;

import java.util.stream.Stream;

import java.util.stream.StreamSupport;

import static java.lang.StackStreamFactory.WalkerState.*;

/**

 * StackStreamFactory class provides static factory methods

 * to get different kinds of stack walker/traverser.

 *

 * AbstractStackWalker provides the basic stack walking support

 * fetching stack frames from VM in batches.

 *

 * AbstractStackWalker subclass is specialized for a specific kind of stack traversal

 * to avoid overhead of Stream/Lambda

 * 1. Support traversing Stream<StackFrame>

 * 2. StackWalker::getCallerClass

 * 3. Throwable::init and Throwable::getStackTrace

 * 4. AccessControlContext getting ProtectionDomain

 */

final class StackStreamFactory {

    private StackStreamFactory() {}

    // Stack walk implementation classes to be excluded during stack walking

    // lazily add subclasses when they are loaded.

    private final static Set<Class<?>> stackWalkImplClasses = init();

    private static final int SMALL_BATCH       = 8;

    private static final int BATCH_SIZE        = 32;

    private static final int LARGE_BATCH_SIZE  = 256;

    private static final int MIN_BATCH_SIZE    = SMALL_BATCH;

    // These flags must match the values maintained in the VM

    @Native private static final int DEFAULT_MODE              = 0x0;

    @Native private static final int FILL_CLASS_REFS_ONLY      = 0x2;

    @Native private static final int FILTER_FILL_IN_STACKTRACE = 0x10;

    @Native private static final int SHOW_HIDDEN_FRAMES        = 0x20;  // LambdaForms are hidden by the VM

    @Native private static final int FILL_LIVE_STACK_FRAMES    = 0x100;

    /*

     * For Throwable to use StackWalker, set useNewThrowable to true.

     * Performance work and extensive testing is needed to replace the

     * VM built-in backtrace filled in Throwable with the StackWalker.

     */

    final static boolean useNewThrowable = getProperty("stackwalk.newThrowable", false);

    final static boolean isDebug = getProperty("stackwalk.debug", false);

    static <T> StackFrameTraverser<T>

        makeStackTraverser(StackWalker walker, Function<? super Stream<StackFrame>, ? extends T> function)

    {

        if (walker.hasLocalsOperandsOption())

            return new LiveStackInfoTraverser<T>(walker, function);

        else

            return new StackFrameTraverser<T>(walker, function);

    }

    /**

     * Gets a stack stream to find caller class.

     */

    static CallerClassFinder makeCallerFinder(StackWalker walker) {

        return new CallerClassFinder(walker);

    }

    static boolean useStackTrace(Throwable t) {

        if (t instanceof VirtualMachineError)

            return false;

        return VM.isBooted() && StackStreamFactory.useNewThrowable;

    }

    /*

     * This should only be used by Throwable::<init>.

     */

    static StackTrace makeStackTrace(Throwable ex) {

        return StackTrace.dump(ex);

    }

    /*

     * This creates StackTrace for Thread::dumpThread to use.

     */

    static StackTrace makeStackTrace() {

        return StackTrace.dump();

    }

    enum WalkerState {

        NEW,     // the stream is new and stack walking has not started

        OPEN,    // the stream is open when it is being traversed.

        CLOSED;  // the stream is closed when the stack walking is done

    }

    static abstract class AbstractStackWalker<T> {

        protected final StackWalker walker;

        protected final Thread thread;

        protected final int maxDepth;

        protected final long mode;

        protected int depth;                 // traversed stack depth

        protected FrameBuffer frameBuffer;   // buffer for VM to fill in

        protected long anchor;

        // buffers to fill in stack frame information

        protected AbstractStackWalker(StackWalker walker, int mode) {

            this(walker, mode, Integer.MAX_VALUE);

        }

        protected AbstractStackWalker(StackWalker walker, int mode, int maxDepth) {

            this.thread = Thread.currentThread();

            this.mode = toStackWalkMode(walker, mode);

            this.walker = walker;

            this.maxDepth = maxDepth;

            this.depth = 0;

        }

        private int toStackWalkMode(StackWalker walker, int mode) {

            int newMode = mode;

            if (walker.hasOption(Option.SHOW_HIDDEN_FRAMES) &&

                    !fillCallerClassOnly(newMode) /* don't show hidden frames for getCallerClass */)

                newMode |= SHOW_HIDDEN_FRAMES;

            if (walker.hasLocalsOperandsOption())

                newMode |= FILL_LIVE_STACK_FRAMES;

            return newMode;

        }

        private boolean fillCallerClassOnly(int mode) {

            return (mode|FILL_CLASS_REFS_ONLY) != FILL_CLASS_REFS_ONLY;

        }

        /**

         * A callback method to consume the stack frames.  This method is invoked

         * once stack walking begins (i.e. it is only invoked when walkFrames is called).

         *

         * Each specialized AbstractStackWalker subclass implements the consumeFrames method

         * to control the following:

         * 1. fetch the subsequent batches of stack frames

         * 2. reuse or expand the allocated buffers

         * 3. create specialized StackFrame objects

         *

         * @return the number of consumed frames

         */

         protected abstract T consumeFrames();

        /**

         * Initialize FrameBuffer.  Subclass should implement this method to

         * create its custom frame buffers.

         */

         protected abstract void initFrameBuffer();

        /**

         * Returns the suggested next batch size.

         *

         * Subclass should override this method to change the batch size

         *

         * @param lastBatchFrameCount number of frames in the last batch; or zero

         * @return suggested batch size

         */

        protected abstract int batchSize(int lastBatchFrameCount);

        /*

         * Returns the next batch size, always >= minimum batch size (32)

         *

         * Subclass may override this method if the minimum batch size is different.

         */

        protected int getNextBatchSize() {

            int lastBatchSize = depth == 0 ? 0 : frameBuffer.curBatchFrameCount();

            int nextBatchSize = batchSize(lastBatchSize);

            if (isDebug) {

                System.err.println("last batch size = " + lastBatchSize +

                                   " next batch size = " + nextBatchSize);

            }

            return nextBatchSize >= MIN_BATCH_SIZE ? nextBatchSize : MIN_BATCH_SIZE;

        }

        /*

         * Checks if this stream is in the given state. Otherwise, throws IllegalStateException.

         *

         * VM also validates this stream if it's anchored for stack walking

         * when stack frames are fetched for each batch.

         */

        final void checkState(WalkerState state) {

            if (thread != Thread.currentThread()) {

                throw new IllegalStateException("Invalid thread walking this stack stream: " +

                        Thread.currentThread().getName() + " " + thread.getName());

            }

            switch (state) {

                case NEW:

                    if (this.anchor != 0) {

                        throw new IllegalStateException("This stack stream is being reused.");

                    }

                    break;

                case OPEN:

                    if (this.anchor <= 0) {

                        throw new IllegalStateException("This stack stream is not valid for walking");

                    }

                    break;

                case CLOSED:

                    if (this.anchor != -1L) {

                        throw new IllegalStateException("This stack stream is not closed.");

                    }

            }

        }

        /*

         * Close this stream.  This stream becomes invalid to walk.

         */

        private void close() {

            this.anchor = -1L;

        }

        /*

         * Walks stack frames until {@link #consumeFrames} is done consuming

         * the frames it is interested in.

         */

        final T walk() {

            checkState(NEW);

            try {

                // VM will need to stablize the stack before walking.  It will invoke

                // the AbstractStackWalker::doStackWalk method once it fetches the first batch.

                // the callback will be invoked within the scope of the callStackWalk frame.

                return beginStackWalk();

            } finally {

                close();  // done traversal; close the stream

            }

        }

        private boolean skipReflectionFrames() {

            return !walker.hasOption(Option.SHOW_REFLECT_FRAMES) &&

                       !walker.hasOption(Option.SHOW_HIDDEN_FRAMES);

        }

        /*

         * Returns {@code Class} object at the current frame;

         * or {@code null} if no more frame. If advanceToNextBatch is true,

         * it will only fetch the next batch.

         */

        final Class<?> peekFrame() {

            while (frameBuffer.isActive() && depth < maxDepth) {

                if (frameBuffer.isEmpty()) {

                    // fetch another batch of stack frames

                    getNextBatch();

                } else {

                    Class<?> c = frameBuffer.get();

                    if (skipReflectionFrames() && isReflectionFrame(c)) {

                        if (isDebug)

                            System.err.println("  skip: frame " + frameBuffer.getIndex() + " " + c);

                        frameBuffer.next();

                        depth++;

                        continue;

                    } else {

                        return c;

                    }

                }

            }

            return null;

        }

        /*

         * This method is only invoked by VM.

         *

         * It will invoke the consumeFrames method to start the stack walking

         * with the first batch of stack frames.  Each specialized AbstractStackWalker

         * subclass implements the consumeFrames method to control the following:

         * 1. fetch the subsequent batches of stack frames

         * 2. reuse or expand the allocated buffers

         * 3. create specialized StackFrame objects

         */

        private Object doStackWalk(long anchor, int skipFrames, int batchSize,

                                                int bufStartIndex, int bufEndIndex) {

            checkState(NEW);

            frameBuffer.check(skipFrames);

            if (isDebug) {

                System.err.format("doStackWalk: skip %d start %d end %d%n",

                        skipFrames, bufStartIndex, bufEndIndex);

            }

            this.anchor = anchor;  // set anchor for this bulk stack frame traversal

            frameBuffer.setBatch(bufStartIndex, bufEndIndex);

            // traverse all frames and perform the action on the stack frames, if specified

            return consumeFrames();

        }

        /*

         * Get next batch of stack frames.

         */

        private int getNextBatch() {

            int nextBatchSize = Math.min(maxDepth - depth, getNextBatchSize());

            if (!frameBuffer.isActive() || nextBatchSize <= 0) {

                if (isDebug) {

                    System.out.format("  more stack walk done%n");

                }

                frameBuffer.freeze();   // stack walk done

                return 0;

            }

            return fetchStackFrames(nextBatchSize);

        }

        /*

         * This method traverses the next stack frame and returns the Class

         * invoking that stack frame.

         *

         * This method can only be called during the walk method.  This is intended

         * to be used to walk the stack frames in one single invocation and

         * this stack stream will be invalidated once walk is done.

         *

         * @see #tryNextFrame

         */

        final Class<?> nextFrame() {

            if (!hasNext()) {

                return null;

            }

            Class<?> c = frameBuffer.next();

            depth++;

            return c;

        }

        /*

         * Returns true if there is next frame to be traversed.

         * This skips hidden frames unless this StackWalker has

         * {@link Option#SHOW_REFLECT_FRAMES}

         */

        final boolean hasNext() {

            return peekFrame() != null;

        }

        /**

         * Begin stack walking - pass the allocated arrays to the VM to fill in

         * stack frame information.

         *

         * VM first anchors the frame of the current thread.  A traversable stream

         * on this thread's stack will be opened.  The VM will fetch the first batch

         * of stack frames and call AbstractStackWalker::doStackWalk to invoke the

         * stack walking function on each stack frame.

         *

         * If all fetched stack frames are traversed, AbstractStackWalker::fetchStackFrames will

         * fetch the next batch of stack frames to continue.

         */

        private T beginStackWalk() {

            // initialize buffers for VM to fill the stack frame info

            initFrameBuffer();

            return callStackWalk(mode, 0,

                                 frameBuffer.curBatchFrameCount(),

                                 frameBuffer.startIndex(),

                                 frameBuffer.classes,

                                 frameBuffer.stackFrames);

        }

        /*

         * Fetches stack frames.

         *

         * @params batchSize number of elements of the frame  buffers for this batch

         * @returns number of frames fetched in this batch

         */

        private int fetchStackFrames(int batchSize) {

            int startIndex = frameBuffer.startIndex();

            frameBuffer.resize(startIndex, batchSize);

            int endIndex = fetchStackFrames(mode, anchor, batchSize,

                                            startIndex,

                                            frameBuffer.classes,

                                            frameBuffer.stackFrames);

            if (isDebug) {

                System.out.format("  more stack walk requesting %d got %d to %d frames%n",

                                  batchSize, frameBuffer.startIndex(), endIndex);

            }

            int numFrames = endIndex - startIndex;

            if (numFrames == 0) {

                frameBuffer.freeze(); // done stack walking

            } else {

                frameBuffer.setBatch(startIndex, endIndex);

            }

            return numFrames;

        }

        /**

         * Begins stack walking.  This method anchors this frame and invokes

         * AbstractStackWalker::doStackWalk after fetching the firt batch of stack frames.

         *

         * @param mode        mode of stack walking

         * @param skipframes  number of frames to be skipped before filling the frame buffer.

         * @param batchSize   the batch size, max. number of elements to be filled in the frame buffers.

         * @param startIndex  start index of the frame buffers to be filled.

         * @param classes     Classes buffer of the stack frames

         * @param frames      StackFrame buffer, or null

         * @return            Result of AbstractStackWalker::doStackWalk

         */

        private native T callStackWalk(long mode, int skipframes,

                                       int batchSize, int startIndex,

                                       Class<?>[] classes,

                                       StackFrame[] frames);

        /**

         * Fetch the next batch of stack frames.

         *

         * @param mode        mode of stack walking

         * @param anchor

         * @param batchSize   the batch size, max. number of elements to be filled in the frame buffers.

         * @param startIndex  start index of the frame buffers to be filled.

         * @param classes     Classes buffer of the stack frames

         * @param frames      StackFrame buffer, or null

         *

         * @return the end index to the frame buffers

         */

        private native int fetchStackFrames(long mode, long anchor,

                                            int batchSize, int startIndex,

                                            Class<?>[] classes,

                                            StackFrame[] frames);

        /*

         * Frame buffer

         *

         * Each specialized AbstractStackWalker subclass may subclass the FrameBuffer.

         */

        class FrameBuffer {

            static final int START_POS = 2;     // 0th and 1st elements are reserved

            // buffers for VM to fill stack frame info

            int currentBatchSize;    // current batch size

            Class<?>[] classes;      // caller class for fast path

            StackFrame[] stackFrames;

            int origin;         // index to the current traversed stack frame

            int fence;          // index to the last frame in the current batch

            FrameBuffer(int initialBatchSize) {

                if (initialBatchSize < MIN_BATCH_SIZE) {

                    throw new IllegalArgumentException(initialBatchSize + " < minimum batch size: " + MIN_BATCH_SIZE);

                }

                this.origin = START_POS;

                this.fence = 0;

                this.currentBatchSize = initialBatchSize;

                this.classes = new Class<?>[currentBatchSize];

            }

            int curBatchFrameCount() {

                return currentBatchSize-START_POS;

            }

            /*

             * Tests if this frame buffer is empty.  All frames are fetched.

             */

            final boolean isEmpty() {

                return origin >= fence || (origin == START_POS && fence == 0);

            }

            /*

             * Freezes this frame buffer.  The stack stream source is done fetching.

             */

            final void freeze() {

                origin = 0;

                fence = 0;

            }

            /*

             * Tests if this frame buffer is active.  It is inactive when

             * it is done for traversal.  All stack frames have been traversed.

             */

            final boolean isActive() {

                return origin > 0 && (fence == 0 || origin < fence || fence == currentBatchSize);

            }

            /**

             * Gets the class at the current frame and move to the next frame.

             */

            final Class<?> next() {

                if (isEmpty()) {

                    throw new NoSuchElementException("origin=" + origin + " fence=" + fence);

                }

                Class<?> c = classes[origin++];

                if (isDebug) {

                    int index = origin-1;

                    System.out.format("  next frame at %d: %s (origin %d fence %d)%n", index,

                                      Objects.toString(c), index, fence);

                }

                return c;

            }

            /**

             * Gets the class at the current frame.

             */