/*
 * Copyright (c) 1994, 2014, 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.reflect.ReflectionFactory;

import java.lang.reflect.Method;
import java.lang.reflect.Modifier;
import java.security.AccessController;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A table of methods with different operations for adding and removing methods.
 * It implements {@link Iterable} which iterates {@link java.lang.reflect.Method} objects
 * in order they were added to the table.
 */
interface MethodTable extends Iterable<Method> {

    /**
     * When requested {@code expectedMaxSize <= MAX_ARRAY_SIZE} then
     * {@link java.lang.MethodTable.SimpleArrayImpl} is created
     * else {@link HashArrayImpl} is created.
     */
    int MAX_ARRAY_SIZE = 20;

    /**
     * Constructs new instance of MethodTable with enough capacity to
     * hold {@code expectedMaxSize} methods.
     *
     * @param expectedMaxSize expected maximum size of MethodTable
     * @return new instance of MethodTable
     */
    static MethodTable newInstance(int expectedMaxSize) {
        return expectedMaxSize <= MAX_ARRAY_SIZE
               ? new SimpleArrayImpl(expectedMaxSize)
               : new HashArrayImpl(expectedMaxSize);
    }

    /**
     * Unconditionally adds given {@code method} to this MethodTable.
     *
     * @param method a method to add
     */
    void add(Method method);

    /**
     * Adds given {@code method} to this MethodTable unless a method
     * with same signature already exists and it's
     * {@link java.lang.reflect.Method#getDeclaringClass() declaring class}
     * is equal to given {@code declaringClass}.
     *
     * @param method         a method to add
     * @param declaringClass the class to check against declaring classes
     *                       of existing methods with same signature
     */
    void addUnlessDeclaredExists(Method method, Class<?> declaringClass);

    /**
     * Each existing method with same signature as given {@code method}
     * is compared in turn with it and the following actions are taken:
     * <ul>
     * <li>if given method is same method as existing method,
     * the operation completes without adding given method.</li>
     * <li>if existing method is declared by given {@code declaringClass},
     * the operation completes without adding given method.</li>
     * <li>if existing method is not abstract and either existing method
     * overrides given method or existing method is declared by class and given
     * method is declared by interface, the operation completes without
     * adding given method.</li>
     * <li>if given method is not abstract and either given method overrides
     * existing method or given method is declared by class and existing
     * method is declared by interface, then existing method is removed
     * from this MethodTable.</li>
     * <li>if there are no more existing methods then given method is added
     * to this MethodTable and operation completes else next existing
     * method is taken into consideration.</li>
     * </ul>
     *
     * @param method a method to consolidate with existing methods of same
     *               signature
     */
    void consolidate(Method method, Class<?> declaringClass);

    /**
     * @return the size of this MethodTable
     */
    int getSize();

    /**
     * Clears this MethodTable.
     */
    void clear();

    /**
     * @return new array of methods contained in this MethodTable
     * in order they were added to this table.
     */
    default Method[] getMethods() {
        Method[] methods = new Method[getSize()];
        int i = 0;
        for (Method m : this) {
            methods[i++] = m;
        }
        return methods;
    }


    /**
     * @return the 1st among the methods with the most specific return type
     * if there is one or null if there are no methods in this MethodTable.
     */
    default Method getFirstMethodWithMostSpecificReturnType() {
        Method res = null;
        for (Method m : this) {
            if (res == null || (
                               res.getReturnType() != m.getReturnType() &&
                               res.getReturnType().isAssignableFrom(m.getReturnType())
            )) {
                res = m;
            }
        }
        return res;
    }

    /**
     * A doubly-linked list of nodes. Each DLNode starts life as
     * it's own doubly-linked singleton list.<p>
     * {@link #unlink(Anchor anchor)} un-links a DLNode from a doubly-linked
     * list with other nodes and liberates it so that it forms it's
     * own singleton list. It also decrements {@code anchor}'s size.<p>
     * {@link #linkBefore(Anchor anchor)} inserts a DLNode into the doubly-linked
     * list before the {@code anchor} and increments it's size.
     */
    interface DLNode {
        DLNode getNextDln();

        void setNextDln(DLNode nextDln);

        DLNode getPrevDln();

        void setPrevDln(DLNode prevDln);

        /**
         * Insert {@code this} DLNode before {@code anchor}
         */
        default void linkBefore(Anchor anchor) {
            // should be free before linking
            assert this.getNextDln() == this &&
                   this.getPrevDln() == this;
            DLNode prev = anchor.getPrevDln();
            this.setNextDln(anchor);
            anchor.setPrevDln(this);
            prev.setNextDln(this);
            this.setPrevDln(prev);
            anchor.addToSize(1);
        }

        /**
         * Remove {@code this} DLNode from doubly-linked list
         */
        default void unlink(Anchor anchor) {
            DLNode next = this.getNextDln();
            DLNode prev = this.getPrevDln();
            // should be linked before un-linking
            assert next != this && prev != this;
            next.setPrevDln(prev);
            prev.setNextDln(next);
            this.setNextDln(this);
            this.setPrevDln(this);
            anchor.addToSize(-1);
        }

        /**
         * Anchor is a {@link DLNode} which keeps track
         * of doubly-linked list size.
         */
        interface Anchor extends DLNode {
            void addToSize(int increment);
        }
    }

    /**
     * A node forming a linked-list of Method objects that share the same signature
     * and a key with equals/hashCode that compares method signature.
     * It also implements {@link DLNode} so it forms a separate doubly-linked list
     * with other DLNode(s) to keep insertion order.
     */
    final class MethodNode implements DLNode {
        final Method method;
        private final int hash;
        MethodNode next;

        MethodNode(Method method) {
            this.method = method;
            this.hash = method.getReturnType().hashCode() ^
                        method.getName().hashCode() ^
                        reflectionFactory.methodParameterTypesHashCode(method);
        }

        void add(MethodNode other, Anchor anchor) {
            other.next = this.next;
            this.next = other;
            other.linkBefore(anchor);
        }

        void addUnlessDeclaredExists(MethodNode other,
                                     Class<?> declaringClass,
                                     Anchor anchor) {
            for (MethodNode node = this;
                 node.method.getDeclaringClass() != declaringClass;
                 node = node.next
            ) {
                if (node.next == null) {
                    node.next = other;
                    other.linkBefore(anchor);
                    break;
                }
            }
        }

        MethodNode consolidate(MethodNode other,
                               Class<?> declaringClass,
                               Anchor anchor) {
            Class<?> thisCl = this.method.getDeclaringClass();
            Class<?> otherCl = other.method.getDeclaringClass();

            if (thisCl == otherCl ||         // this.method is the same as other.method OR
                thisCl == declaringClass) {  // this.method is declared by declaringClass
                // complete without adding other
                return this;
            }

            boolean thisAbstract = Modifier.isAbstract(this.method.getModifiers());

            if (!thisAbstract &&                    // this.method is non-abstract...
                otherCl.isAssignableFrom(thisCl)) { // ...and overrides other.method
                // complete without adding other
                return this;
            }

            boolean thisInterface = thisCl.isInterface();
            boolean otherInterface = otherCl.isInterface();

            if (!thisAbstract && !thisInterface && // this.method is non-abstract class method...
                otherInterface) {                  //...which wins over interface other.method
                // complete without adding other
                return this;
            }

            boolean otherAbstract = Modifier.isAbstract(other.method.getModifiers());

            if (!otherAbstract &&                   // other.method is non-abstract...
                thisCl.isAssignableFrom(otherCl)) { // ...and overrides this.method
                // remove this and...
                this.unlink(anchor);
                if (next == null) { // ...add other
                    other.linkBefore(anchor);
                    return other;
                } else {            // ...continue with other
                    return next.consolidate(other, declaringClass, anchor);
                }
            }

            if (!otherAbstract && !otherInterface && // other.method is non-abstract class method...
                thisInterface) {                     //...which wins over interface this.method
                // remove this and...
                this.unlink(anchor);
                if (next == null) { // ...add other
                    other.linkBefore(anchor);
                    return other;
                } else {            // ...continue with other
                    return next.consolidate(other, declaringClass, anchor);
                }
            }

            // else keep this and...
            if (next == null) { // ...add other
                other.linkBefore(anchor);
                next = other;
            } else {            //...continue with other
                next = next.consolidate(other, declaringClass, anchor);
            }
            return this;
        }

        @Override
        public int hashCode() {
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == this) return true;
            if (!(obj instanceof MethodNode)) return false;
            MethodNode other = (MethodNode) obj;
            return this.method.getReturnType() == other.method.getReturnType() &&
                   this.method.getName() == other.method.getName() && // Method.name is interned
                   reflectionFactory.methodParameterTypesEquals(this.method, other.method);
        }

        // we just need to compare method parameter types

        private static final ReflectionFactory reflectionFactory
        = AccessController.doPrivileged(new ReflectionFactory.GetReflectionFactoryAction());

        // DLNode implementation

        private DLNode nextDln = this;
        private DLNode prevDln = this;

        @Override
        public DLNode getNextDln() {
            return nextDln;
        }

        @Override
        public void setNextDln(DLNode nextDln) {
            this.nextDln = nextDln;
        }

        @Override
        public DLNode getPrevDln() {
            return prevDln;
        }

        @Override
        public void setPrevDln(DLNode prevDln) {
            this.prevDln = prevDln;
        }
    }

    /**
     * MethodTable implementation based on {@link HashArray}.
     * It also implements {@link DLNode.Anchor} to
     * form a doubly-linked list with other DLNode(s).
     */
    final class HashArrayImpl extends HashArray<MethodNode> implements MethodTable, DLNode.Anchor {

        HashArrayImpl(int expectedMaxSize) {
            super(expectedMaxSize);
        }

        @Override
        public void add(Method method) {
            MethodNode n = new MethodNode(method);
            MethodNode n0 = putIfAbsent(n);
            if (n0 == null) {
                n.linkBefore(this);
            } else {
                n0.add(n, this);
            }
        }

        @Override
        public void addUnlessDeclaredExists(Method method, Class<?> declaringClass) {
            MethodNode n = new MethodNode(method);
            MethodNode n0 = putIfAbsent(n);
            if (n0 == null) {
                n.linkBefore(this);
            } else {
                n0.addUnlessDeclaredExists(n, declaringClass, this);
            }
        }

        @Override
        public void consolidate(Method method, Class<?> declaringClass) {
            MethodNode n = new MethodNode(method);
            MethodNode n0 = putIfAbsent(n);
            if (n0 == null) {
                n.linkBefore(this);
            } else {
                MethodNode n1 = n0.consolidate(n, declaringClass, this);
                if (n1 != n0) {
                    put(n1);
                }
            }
        }

        @Override
        public int getSize() {
            return size;
        }

        @Override
        public void clear() {
            super.clear();
            nextDln = prevDln = this;
            size = 0;
        }

        // Iterable<Method> implementation

        @Override
        public Iterator<Method> iterator() {
            return new Iterator<Method>() {

                DLNode dln = HashArrayImpl.this.getNextDln();

                @Override
                public boolean hasNext() {
                    return dln != HashArrayImpl.this;
                }

                @Override
                public Method next() {
                    if (!hasNext()) {
                        throw new NoSuchElementException();
                    }
                    Method result = ((MethodNode) dln).method;
                    dln = dln.getNextDln();
                    return result;
                }
            };
        }

        // DLNode.Anchor implementation

        private DLNode nextDln = this;
        private DLNode prevDln = this;
        private int size;

        @Override
        public DLNode getNextDln() {
            return nextDln;
        }

        @Override
        public void setNextDln(DLNode nextDln) {
            this.nextDln = nextDln;
        }

        @Override
        public DLNode getPrevDln() {
            return prevDln;
        }

        @Override
        public void setPrevDln(DLNode prevDln) {
            this.prevDln = prevDln;
        }

        @Override
        public void addToSize(int increment) {
            size += increment;
        }
    }

    /**
     * Simple array based MethodTable implementation for small number of methods.
     */
    final class SimpleArrayImpl implements MethodTable {

        private final Method[] methods;
        private int hwm; // High Water Mark

        SimpleArrayImpl(int expectedMaxSize) {
            methods = new Method[expectedMaxSize];
        }

        @Override
        public void add(Method method) {
            methods[hwm++] = method;
        }

        @Override
        public void addUnlessDeclaredExists(Method otherM, Class<?> declaringClass) {
            for (int i = 0; i < hwm; i++) {
                Method thisM = methods[i];
                if (thisM == null ||                                   // mind the gap
                    thisM.getReturnType() != otherM.getReturnType() || // not same signature
                    thisM.getName() != otherM.getName() ||             // Method.name is interned
                    !MethodNode.reflectionFactory.methodParameterTypesEquals(thisM, otherM)) {
                    continue;
                }
                // thisM has same signature as otherM

                if (thisM.getDeclaringClass() == declaringClass) {
                    return;
                }
                // continue with next thisM
            }
            // add otherM
            methods[hwm++] = otherM;
        }

        @Override
        public void consolidate(Method otherM, Class<?> declaringClass) {
            for (int i = 0; i < hwm; i++) {
                Method thisM = methods[i];
                if (thisM == null ||                                   // mind the gap
                    thisM.getReturnType() != otherM.getReturnType() || // not same signature
                    thisM.getName() != otherM.getName() ||             // Method.name is interned
                    !MethodNode.reflectionFactory.methodParameterTypesEquals(thisM, otherM)) {
                    continue;
                }
                // thisM has same signature as otherM

                Class<?> thisCl = thisM.getDeclaringClass();
                Class<?> otherCl = otherM.getDeclaringClass();

                if (thisCl == otherCl ||         // thisM is the same as otherM OR
                    thisCl == declaringClass) {  // thisM is declared by declaringClass
                    // complete without adding otherM
                    return;
                }

                boolean thisAbstract = Modifier.isAbstract(thisM.getModifiers());

                if (!thisAbstract &&                    // thisM is non-abstract...
                    otherCl.isAssignableFrom(thisCl)) { // ...and overrides otherM
                    // complete without adding otherM
                    return;
                }

                boolean thisInterface = thisCl.isInterface();
                boolean otherInterface = otherCl.isInterface();

                if (!thisAbstract && !thisInterface && // this.method is non-abstract class method...
                    otherInterface) {                  //...which wins over interface other.method
                    // complete without adding otherM
                    return;
                }

                boolean otherAbstract = Modifier.isAbstract(otherM.getModifiers());

                if (!otherAbstract &&                   // other.method is non-abstract...
                    thisCl.isAssignableFrom(otherCl)) { // ...and overrides this.method
                    // remove this
                    methods[i] = null;
                    continue;
                }

                if (!otherAbstract && !otherInterface && // other.method is non-abstract class method...
                    thisInterface) {                     //...which wins over interface this.method
                    // remove this
                    methods[i] = null;
                }
                // continue with next thisM
            }
            // add otherM
            methods[hwm++] = otherM;
        }

        @Override
        public int getSize() {
            int size = 0;
            for (int i = 0; i < hwm; i++) {
                if (methods[i] != null) {
                    size++;
                }
            }
            return size;
        }

        @Override
        public void clear() {
            Arrays.fill(methods, null);
            hwm = 0;
        }

        @Override
        public Iterator<Method> iterator() {
            return new Iterator<Method>() {
                int i = 0;
                Method next;

                private Method nextMethod() {
                    while (next == null && i < hwm) next = methods[i++];
                    return next;
                }

                @Override
                public boolean hasNext() {
                    return nextMethod() != null;
                }

                @Override
                public Method next() {
                    Method m = nextMethod();
                    if (m == null) throw new NoSuchElementException();
                    next = null;
                    return m;
                }
            };
        }
    }
}