/*
 * Copyright (c) 2016, 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 jdk.internal.misc.Unsafe;
import jdk.internal.vm.annotation.ForceInline;
import jdk.internal.vm.annotation.Stable;

import java.lang.ref.PhantomReference;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;

/**
 * Lazily associate a computed value with (potentially) every type.
 * For example, if a dynamic language needs to construct a message dispatch
 * table for each class encountered at a message send call site,
 * it can use a {@code ClassValue} to cache information needed to
 * perform the message send quickly, for each class encountered.
 * @author John Rose, JSR 292 EG
 * @since 1.7
 */
public abstract class ClassValue<T> {
    /**
     * Sole constructor.  (For invocation by subclass constructors, typically
     * implicit.)
     */
    protected ClassValue() {
    }

    /**
     * Computes the given class's derived value for this {@code ClassValue}.
     * <p>
     * This method will be invoked within the first thread that accesses
     * the value with the {@link #get get} method.
     * <p>
     * Normally, this method is invoked at most once per class,
     * but it may be invoked again if there has been a call to
     * {@link #remove remove}.
     * <p>
     * If this method throws an exception, the corresponding call to {@code get}
     * will terminate abnormally with that exception, and no class value will be recorded.
     *
     * @param type the type whose class value must be computed
     * @return the newly computed value associated with this {@code ClassValue}, for the given class or interface
     * @see #get
     * @see #remove
     */
    protected abstract T computeValue(Class<?> type);

    /**
     * Returns the value for the given class.
     * If no value has yet been computed, it is obtained by
     * an invocation of the {@link #computeValue computeValue} method.
     * <p>
     * The actual installation of the value on the class
     * is performed atomically.
     * At that point, if several racing threads have
     * computed values, one is chosen, and returned to
     * all the racing threads.
     * <p>
     * The {@code type} parameter is typically a class, but it may be any type,
     * such as an interface, a primitive type (like {@code int.class}), or {@code void.class}.
     * <p>
     * In the absence of {@code remove} calls, a class value has a simple
     * state diagram:  uninitialized and initialized.
     * When {@code remove} calls are made,
     * the rules for value observation are more complex.
     * See the documentation for {@link #remove remove} for more information.
     *
     * @param type the type whose class value must be computed or retrieved
     * @return the current value associated with this {@code ClassValue}, for the given class or interface
     * @throws NullPointerException if the argument is null
     * @see #remove
     * @see #computeValue
     */
    @SuppressWarnings("unchecked")
    @ForceInline
    public T get(Class<?> type) {
        ClassValueMap map = type.classValueMap;
        Object value;
        if (map != null) {
            value = map.get(key);
            if (value != null && !(value instanceof Removed)) {
                return (value == NULL_MASK) ? null : (T) value;
            }
        } else {
            value = null;
        }
        return getSlow(type, value);
    }
    // ...the rest in separate method
    @SuppressWarnings("unchecked")
    private T getSlow(Class<?> type, Object oldValue) {
        ClassValueMap.expungeStaleEntries();
        ClassValueMap map = getMap(type);
        while (true) {
            // assert oldValue == null || oldValue instanceof Removed;
            T newValue = computeValue(type);
            if (oldValue == null) {
                oldValue = map.putIfAbsent(key, (newValue == null) ? NULL_MASK : newValue);
                if (oldValue == null) {
                    return newValue;
                } else {
                    // another thread has beaten us
                    if (!(oldValue instanceof Removed)) {
                        return (oldValue == NULL_MASK) ? null : (T) oldValue;
                    }
                }
            } else {
                // assert oldValue instanceof Removed;
                if (map.replace(key, oldValue, (newValue == null) ? NULL_MASK : newValue)) {
                    // this only succeeds if oldValue is still the same instance of
                    // Removed as observed before computeValue invocation
                    return newValue;
                } else {
                    // another thread has beaten us
                    oldValue = map.get(key);
                    if (oldValue != null && !(oldValue instanceof Removed)) {
                        return (oldValue == NULL_MASK) ? null : (T) oldValue;
                    }
                }
            }
            // retry compute since we observed another version of Removed
            // as was current before compute which means that there was
            // at least one value present in between time which means
            // that the result of our compute is stale.
        }
    }

    /**
     * Removes the associated value for the given class.
     * If this value is subsequently {@linkplain #get read} for the same class,
     * its value will be reinitialized by invoking its {@link #computeValue computeValue} method.
     * This may result in an additional invocation of the
     * {@code computeValue} method for the given class.
     * <p>
     * In order to explain the interaction between {@code get} and {@code remove} calls,
     * we must model the state transitions of a class value to take into account
     * the alternation between uninitialized and initialized states.
     * To do this, number these states sequentially from zero, and note that
     * uninitialized (or removed) states are numbered with even numbers,
     * while initialized (or re-initialized) states have odd numbers.
     * <p>
     * When a thread {@code T} removes a class value in state {@code 2N},
     * nothing happens, since the class value is already uninitialized.
     * Otherwise, the state is advanced atomically to {@code 2N+1}.
     * <p>
     * When a thread {@code T} queries a class value in state {@code 2N},
     * the thread first attempts to initialize the class value to state {@code 2N+1}
     * by invoking {@code computeValue} and installing the resulting value.
     * <p>
     * When {@code T} attempts to install the newly computed value,
     * if the state is still at {@code 2N}, the class value will be initialized
     * with the computed value, advancing it to state {@code 2N+1}.
     * <p>
     * Otherwise, whether the new state is even or odd,
     * {@code T} will discard the newly computed value
     * and retry the {@code get} operation.
     * <p>
     * Discarding and retrying is an important proviso,
     * since otherwise {@code T} could potentially install
     * a disastrously stale value.  For example:
     * <ul>
     * <li>{@code T} calls {@code CV.get(C)} and sees state {@code 2N}
     * <li>{@code T} quickly computes a time-dependent value {@code V0} and gets ready to install it
     * <li>{@code T} is hit by an unlucky paging or scheduling event, and goes to sleep for a long time
     * <li>...meanwhile, {@code T2} also calls {@code CV.get(C)} and sees state {@code 2N}
     * <li>{@code T2} quickly computes a similar time-dependent value {@code V1} and installs it on {@code CV.get(C)}
     * <li>{@code T2} (or a third thread) then calls {@code CV.remove(C)}, undoing {@code T2}'s work
     * <li> the previous actions of {@code T2} are repeated several times
     * <li> also, the relevant computed values change over time: {@code V1}, {@code V2}, ...
     * <li>...meanwhile, {@code T} wakes up and attempts to install {@code V0}; <em>this must fail</em>
     * </ul>
     * We can assume in the above scenario that {@code CV.computeValue} uses locks to properly
     * observe the time-dependent states as it computes {@code V1}, etc.
     * This does not remove the threat of a stale value, since there is a window of time
     * between the return of {@code computeValue} in {@code T} and the installation
     * of the new value.  No user synchronization is possible during this time.
     *
     * @param type the type whose class value must be removed
     * @throws NullPointerException if the argument is null
     */
    public void remove(Class<?> type) {
        ClassValueMap.expungeStaleEntries();
        ClassValueMap map = type.classValueMap;
        if (map != null) {
            Object value, removed = null;
            do {
                value = map.get(key);
                if (value == null || value instanceof Removed) {
                    // non-existence is treated as Removed(V0)
                    // invoking remove() when state is Removed(VN) does not
                    // change it to Removed(VN+1)
                    break;
                }
                if (removed == null) {
                    removed = new Removed();
                }
            } while (!map.replace(key, value, removed));
        }
    }

    // Possible functionality for JSR 292 MR 1
    /*public*/ void put(Class<?> type, T value) {
        ClassValueMap.expungeStaleEntries();
        ClassValueMap map = getMap(type);
        map.put(key, (value == null) ? NULL_MASK : value);
    }

    /// --------
    /// Implementation...
    /// --------

    /**
     * The key used in ClassValueMap for this ClassValue.
     * Since ClassValue(s) are usually assigned to static final fields, it makes
     * sense to promote the key to constant too.
     */
    @Stable
    private final Key key = new Key(this);

    /**
     * Key of a ClassValue and a tracker of the ClassValue at the same time.
     */
    private static final class Key extends PhantomReference<ClassValue<?>> {

        /** Value stream for hash. See similar structure in ThreadLocal. */
        private static final AtomicInteger nextHash = new AtomicInteger();

        /** Good for power-of-two tables. See similar structure in ThreadLocal. */
        private static final int HASH_INCREMENT = 0x61c88647;

        /** Single global queue for all stale keys to be enqueued */
        static final ReferenceQueue<ClassValue<?>> queue = new ReferenceQueue<>();

        @Stable
        private final int hash;

        Key(ClassValue<?> cv) {
            super(cv, queue);
            hash = nextHash.getAndAdd(HASH_INCREMENT);
        }

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

        // equals is identity
    }

    /** A masked null value. */
    private static final Object NULL_MASK = new Object();

    /** Removed value(s) */
    private static final class Removed {}

    /** Return the backing map associated with this type, possibly constructing it. */
    private static ClassValueMap getMap(Class<?> type) {
        ClassValueMap map = type.classValueMap;
        return (map != null) ? map : initializeMap(type);
    }

    private static ClassValueMap initializeMap(Class<?> type) {
        ClassValueMap map = ClassValueMap.create();
        return U.compareAndSwapObject(type, CLASS_VALUE_MAP_OFFSET, null, map)
               ? map
               : (ClassValueMap) U.getObjectVolatile(type, CLASS_VALUE_MAP_OFFSET);
    }

    /** A backing map for all ClassValues in a particular Class.
     */
    static final class ClassValueMap extends LinearProbeHashtable<Key, Object> {
        // eh, needed to silent the gods
        private static final long serialVersionUID = 1L;

        // a node in a linked list of WeakReference(s) to ClassValueMap(s)
        private static final class WeakNode extends WeakReference<ClassValueMap> {
            WeakNode next;
            WeakNode(ClassValueMap map) { super(map); }
        }

        // the head of the linked list of WeakReference(s) to ClassValueMap(s)
        private static final AtomicReference<WeakNode> mapsList = new AtomicReference<>();

        // the lock used to guard expunging logic
        private static final AtomicBoolean expungeInProgress = new AtomicBoolean();

        private ClassValueMap() {
            super(1);
        }

        static ClassValueMap create() {
            ClassValueMap map = new ClassValueMap();
            WeakNode node = new WeakNode(map);
            // register the weakly referenced map into the list
            do {
                node.next = mapsList.get();
            } while (!mapsList.compareAndSet(node.next, node));
            return map;
        }

        static void expungeStaleEntries() {
            // make sure only one thread at a time is expunging stale entries;
            // this is important for correctness so that no stale enqueued key
            // is missed from being removed from any map that might possibly
            // hold it.
            if (!expungeInProgress.get() &&
                expungeInProgress.compareAndSet(false, true)) try {
                expungeStaleEntriesImpl();
            } finally {
                expungeInProgress.set(false);
            }
        }

        private static void expungeStaleEntriesImpl() {
            // start with an empty private list
            WeakNode first = null, last = null;
            // iterate Key(s) of GCed ClassValue(s)
            Key key;
            while ((key = (Key) Key.queue.poll()) != null) {
                // steal any (newly) registered map(s) from the shared 'mapsList'
                // as they might already be holding the stale 'key' that has just
                // been removed from the queue. The following guarantees that
                // no (stale-key, live-map) combination is missed:
                // - a map is 1st registered into the mapsList and then non-stale
                //   keys are inserted into it
                // - a non-stale key becomes stale when a ClassValue that it
                //   phantomly references is GCed; the key is then enqueued
                // - a stale key is 1st removed from the queue and then mapsList
                //   is checked for any (newly) registered map(s)
                if (mapsList.get() != null) {
                    WeakNode stolen = mapsList.getAndSet(null);
                    // add them to the end of current private list
                    if (last != null) {
                        last.next = stolen;
                    } else {
                        // assert first == null;
                        first = stolen;
                    }
                }
                // iterate the accumulated private list of maps
                last = null;
                for (WeakNode node = first; node != null; ) {
                    ClassValueMap map = node.get();
                    if (map == null) {
                        // Class and its ClassValueMap have already been GCed
                        // -> remove the node from the list
                        if (last == null) {
                            first = node = node.next;
                        } else {
                            last.next = node = node.next;
                        }
                    } else {
                        // ClassValueMap is still alive
                        // -> attempt to remove the key from it
                        map.remove(key);
                        // navigate to next in list
                        last = node;
                        node = node.next;
                    }
                }
                // at this time, 'last' points to the last WeakNode in the private
                // list (if any) and the following always holds:
                // assert (first == null) == (last == null);
            }
            // re-insert the stolen and expunged list of map(s) back into shared
            // mapsList
            if (last != null) {
                do {
                    last.next = mapsList.get();
                } while (!mapsList.compareAndSet(last.next, first));
            }
        }
    }

    /** We need to cas */
    private static final Unsafe U = Unsafe.getUnsafe();
    private static final long CLASS_VALUE_MAP_OFFSET;

    static {
        try {
            CLASS_VALUE_MAP_OFFSET = U.objectFieldOffset(
                Class.class.getDeclaredField("classValueMap"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
}