/*

 * Copyright (c) 2010, 2017, 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 jdk.nashorn.internal.runtime;

import static jdk.nashorn.internal.runtime.PropertyHashMap.EMPTY_HASHMAP;

import static jdk.nashorn.internal.runtime.arrays.ArrayIndex.getArrayIndex;

import static jdk.nashorn.internal.runtime.arrays.ArrayIndex.isValidArrayIndex;

import java.io.IOException;

import java.io.ObjectInputStream;

import java.io.ObjectOutputStream;

import java.io.Serializable;

import java.lang.invoke.SwitchPoint;

import java.lang.ref.Reference;

import java.lang.ref.SoftReference;

import java.lang.ref.WeakReference;

import java.util.Arrays;

import java.util.BitSet;

import java.util.Collection;

import java.util.Iterator;

import java.util.NoSuchElementException;

import java.util.Set;

import java.util.WeakHashMap;

import java.util.concurrent.atomic.LongAdder;

import jdk.nashorn.internal.runtime.options.Options;

import jdk.nashorn.internal.scripts.JO;

/**

 * Map of object properties. The PropertyMap is the "template" for JavaScript object

 * layouts. It contains a map with prototype names as keys and {@link Property} instances

 * as values. A PropertyMap is typically passed to the {@link ScriptObject} constructor

 * to form the seed map for the ScriptObject.

 * <p>

 * All property maps are immutable. If a property is added, modified or removed, the mutator

 * will return a new map.

 */

public class PropertyMap implements Iterable<Object>, Serializable {

    private static final int INITIAL_SOFT_REFERENCE_DERIVATION_LIMIT =

            Math.max(0, Options.getIntProperty("nashorn.propertyMap.softReferenceDerivationLimit", 32));

    /** Used for non extensible PropertyMaps, negative logic as the normal case is extensible. See {@link ScriptObject#preventExtensions()} */

    private static final int NOT_EXTENSIBLE         = 0b0000_0001;

    /** Does this map contain valid array keys? */

    private static final int CONTAINS_ARRAY_KEYS    = 0b0000_0010;

    /** Map status flags. */

    private final int flags;

    /** Map of properties. */

    private transient PropertyHashMap properties;

    /** Number of fields in use. */

    private final int fieldCount;

    /** Number of fields available. */

    private final int fieldMaximum;

    /** Length of spill in use. */

    private final int spillLength;

    /** Structure class name */

    private final String className;

    /**

     * Countdown of number of times this property map has been derived from another property map. When it

     * reaches zero, the property map will start using weak references instead of soft references to hold on

     * to its history elements.

     */

    private final int softReferenceDerivationLimit;

    /** A reference to the expected shared prototype property map. If this is set this

     * property map should only be used if it the same as the actual prototype map. */

    private transient SharedPropertyMap sharedProtoMap;

    /** History of maps, used to limit map duplication. */

    private transient WeakHashMap<Property, Reference<PropertyMap>> history;

    /** History of prototypes, used to limit map duplication. */

    private transient WeakHashMap<ScriptObject, SoftReference<PropertyMap>> protoHistory;

    /** SwitchPoints for properties inherited form this map */

    private transient PropertySwitchPoints propertySwitchPoints;

    private transient BitSet freeSlots;

    private static final long serialVersionUID = -7041836752008732533L;

    /**

     * Constructs a new property map.

     *

     * @param properties   A {@link PropertyHashMap} with initial contents.

     * @param fieldCount   Number of fields in use.

     * @param fieldMaximum Number of fields available.

     * @param spillLength  Number of spill slots used.

     */

    private PropertyMap(final PropertyHashMap properties, final int flags, final String className,

                        final int fieldCount, final int fieldMaximum, final int spillLength) {

        this.properties   = properties;

        this.className    = className;

        this.fieldCount   = fieldCount;

        this.fieldMaximum = fieldMaximum;

        this.spillLength  = spillLength;

        this.flags        = flags;

        this.softReferenceDerivationLimit = INITIAL_SOFT_REFERENCE_DERIVATION_LIMIT;

        if (Context.DEBUG) {

            count.increment();

        }

    }

    /**

     * Constructs a clone of {@code propertyMap} with changed properties, flags, or boundaries.

     *

     * @param propertyMap Existing property map.

     * @param properties  A {@link PropertyHashMap} with a new set of properties.

     */

    private PropertyMap(final PropertyMap propertyMap, final PropertyHashMap properties, final int flags, final int fieldCount, final int spillLength, final int softReferenceDerivationLimit) {

        this.properties   = properties;

        this.flags        = flags;

        this.spillLength  = spillLength;

        this.fieldCount   = fieldCount;

        this.fieldMaximum = propertyMap.fieldMaximum;

        this.className    = propertyMap.className;

        // We inherit the parent property propertySwitchPoints instance. It will be cloned when a new listener is added.

        this.propertySwitchPoints = propertyMap.propertySwitchPoints;

        this.freeSlots    = propertyMap.freeSlots;

        this.sharedProtoMap = propertyMap.sharedProtoMap;

        this.softReferenceDerivationLimit = softReferenceDerivationLimit;

        if (Context.DEBUG) {

            count.increment();

            clonedCount.increment();

        }

    }

    /**

     * Constructs an exact clone of {@code propertyMap}.

     *

     * @param propertyMap Existing property map.

      */

    protected PropertyMap(final PropertyMap propertyMap) {

        this(propertyMap, propertyMap.properties, propertyMap.flags, propertyMap.fieldCount, propertyMap.spillLength, propertyMap.softReferenceDerivationLimit);

    }

    private void writeObject(final ObjectOutputStream out) throws IOException {

        out.defaultWriteObject();

        out.writeObject(properties.getProperties());

    }

    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {

        in.defaultReadObject();

        final Property[] props = (Property[]) in.readObject();

        this.properties = EMPTY_HASHMAP.immutableAdd(props);

        assert className != null;

        final Class<?> structure = Context.forStructureClass(className);

        for (final Property prop : props) {

            prop.initMethodHandles(structure);

        }

    }

    /**

     * Public property map allocator.

     *

     * <p>It is the caller's responsibility to make sure that {@code properties} does not contain

     * properties with keys that are valid array indices.</p>

     *

     * @param properties   Collection of initial properties.

     * @param className    class name

     * @param fieldCount   Number of fields in use.

     * @param fieldMaximum Number of fields available.

     * @param spillLength  Number of used spill slots.

     * @return New {@link PropertyMap}.

     */

    public static PropertyMap newMap(final Collection<Property> properties, final String className, final int fieldCount, final int fieldMaximum,  final int spillLength) {

        final PropertyHashMap newProperties = EMPTY_HASHMAP.immutableAdd(properties);

        return new PropertyMap(newProperties, 0, className, fieldCount, fieldMaximum, spillLength);

    }

    /**

     * Public property map allocator. Used by nasgen generated code.

     *

     * <p>It is the caller's responsibility to make sure that {@code properties} does not contain

     * properties with keys that are valid array indices.</p>

     *

     * @param properties Collection of initial properties.

     * @return New {@link PropertyMap}.

     */

    public static PropertyMap newMap(final Collection<Property> properties) {

        return properties == null || properties.isEmpty()? newMap() : newMap(properties, JO.class.getName(), 0, 0, 0);

    }

    /**

     * Return a sharable empty map for the given object class.

     * @param clazz the base object class

     * @return New empty {@link PropertyMap}.

     */

    public static PropertyMap newMap(final Class<? extends ScriptObject> clazz) {

        return new PropertyMap(EMPTY_HASHMAP, 0, clazz.getName(), 0, 0, 0);

    }

    /**

     * Return a sharable empty map.

     *

     * @return New empty {@link PropertyMap}.

     */

    public static PropertyMap newMap() {

        return newMap(JO.class);

    }

    /**

     * Return number of properties in the map.

     *

     * @return Number of properties.

     */

    public int size() {

        return properties.size();

    }

    /**

     * Get the number of property SwitchPoints of this map

     *

     * @return the number of property SwitchPoints

     */

    public int getSwitchPointCount() {

        return propertySwitchPoints == null ? 0 : propertySwitchPoints.getSwitchPointCount();

    }

    /**

     * Add a property switchpoint to this property map for the given {@code key}.

     *

     * @param key the property name

     * @param switchPoint the switchpoint

     */

    public void addSwitchPoint(final String key, final SwitchPoint switchPoint) {

        // We need to clone listener instance when adding a new listener since we share

        // the propertySwitchPoints instance with our parent maps that don't need to see the new listener.

        propertySwitchPoints = PropertySwitchPoints.addSwitchPoint(propertySwitchPoints, key, switchPoint);

    }

    /**

     * Method called when a property of an object using this property map is being created,

     * modified, or deleted. If a switchpoint for the property exists it will be invalidated.

     *

     * @param property The changed property.

     */

    public void propertyChanged(final Property property) {

        if (propertySwitchPoints != null) {

            propertySwitchPoints.invalidateProperty(property);

        }

    }

    /**

     * Method called when the prototype of an object using this property map is changed.

     */

    void protoChanged() {

        if (sharedProtoMap != null) {

            sharedProtoMap.invalidateSwitchPoint();

        }

        if (propertySwitchPoints != null) {

            propertySwitchPoints.invalidateInheritedProperties(this);

        }

    }

    /**

     * Returns a SwitchPoint for use with a property inherited from this or a parent map.

     * If such a switchpoint exists, it will be invalidated when the property is modified

     * in an object using this map. This method returns {@code null} if no swichpoint exists

     * for the property.

     *

     * @param key Property key.

     * @return A {@link SwitchPoint} for the property, or null.

     */

    public synchronized SwitchPoint getSwitchPoint(final String key) {

        if (propertySwitchPoints != null) {

            final Set<SwitchPoint> existingSwitchPoints = propertySwitchPoints.getSwitchPoints(key);

            for (final SwitchPoint switchPoint : existingSwitchPoints) {

                if (switchPoint != null && !switchPoint.hasBeenInvalidated()) {

                    return switchPoint;

                }

            }

        }

        return null;

    }

    /**

     * Add a property to the map, re-binding its getters and setters,

     * if available, to a given receiver. This is typically the global scope. See

     * {@link ScriptObject#addBoundProperties(ScriptObject)}

     *

     * @param property {@link Property} being added.

     * @param bindTo   Object to bind to.

     *

     * @return New {@link PropertyMap} with {@link Property} added.

     */

    PropertyMap addPropertyBind(final AccessorProperty property, final Object bindTo) {

        // We must not store bound property in the history as bound properties can't be reused.

        return addPropertyNoHistory(new AccessorProperty(property, bindTo));

    }

    // Get a logical slot index for a property, with spill slot 0 starting at fieldMaximum.

    private int logicalSlotIndex(final Property property) {

        final int slot = property.getSlot();

        if (slot < 0) {

            return -1;

        }

        return property.isSpill() ? slot + fieldMaximum : slot;

    }

    private int newSpillLength(final Property newProperty) {

        return newProperty.isSpill() ? Math.max(spillLength, newProperty.getSlot() + 1) : spillLength;

    }

    private int newFieldCount(final Property newProperty) {

        return !newProperty.isSpill() ? Math.max(fieldCount, newProperty.getSlot() + 1) : fieldCount;

    }

    private int newFlags(final Property newProperty) {

        return isValidArrayIndex(getArrayIndex(newProperty.getKey())) ? flags | CONTAINS_ARRAY_KEYS : flags;

    }

    // Update the free slots bitmap for a property that has been deleted and/or added. This method is not synchronized

    // as it is always invoked on a newly created instance.

    private void updateFreeSlots(final Property oldProperty, final Property newProperty) {

        // Free slots bitset is possibly shared with parent map, so we must clone it before making modifications.

        boolean freeSlotsCloned = false;

        if (oldProperty != null) {

            final int slotIndex = logicalSlotIndex(oldProperty);

            if (slotIndex >= 0) {

                final BitSet newFreeSlots = freeSlots == null ? new BitSet() : (BitSet)freeSlots.clone();

                assert !newFreeSlots.get(slotIndex);

                newFreeSlots.set(slotIndex);

                freeSlots = newFreeSlots;

                freeSlotsCloned = true;

            }

        }

        if (freeSlots != null && newProperty != null) {

            final int slotIndex = logicalSlotIndex(newProperty);

            if (slotIndex > -1 && freeSlots.get(slotIndex)) {

                final BitSet newFreeSlots = freeSlotsCloned ? freeSlots : ((BitSet)freeSlots.clone());

                newFreeSlots.clear(slotIndex);

                freeSlots = newFreeSlots.isEmpty() ? null : newFreeSlots;

            }

        }

    }

    /**

     * Add a property to the map without adding it to the history. This should be used for properties that

     * can't be shared such as bound properties, or properties that are expected to be added only once.

     *

     * @param property {@link Property} being added.

     * @return New {@link PropertyMap} with {@link Property} added.

     */

    public final PropertyMap addPropertyNoHistory(final Property property) {

        propertyChanged(property);

        return addPropertyInternal(property);

    }

    /**

     * Add a property to the map.  Cloning or using an existing map if available.

     *

     * @param property {@link Property} being added.

     *

     * @return New {@link PropertyMap} with {@link Property} added.

     */

    public final synchronized PropertyMap addProperty(final Property property) {

        propertyChanged(property);

        PropertyMap newMap = checkHistory(property);

        if (newMap == null) {

            newMap = addPropertyInternal(property);

            addToHistory(property, newMap);

        }

        return newMap;

    }

    private PropertyMap deriveMap(final PropertyHashMap newProperties, final int newFlags, final int newFieldCount, final int newSpillLength) {

        return new PropertyMap(this, newProperties, newFlags, newFieldCount, newSpillLength, softReferenceDerivationLimit == 0 ? 0 : softReferenceDerivationLimit - 1);

    }

    private PropertyMap addPropertyInternal(final Property property) {

        final PropertyHashMap newProperties = properties.immutableAdd(property);

        final PropertyMap newMap = deriveMap(newProperties, newFlags(property), newFieldCount(property), newSpillLength(property));

        newMap.updateFreeSlots(null, property);

        return newMap;

    }

    /**

     * Remove a property from a map. Cloning or using an existing map if available.

     *

     * @param property {@link Property} being removed.

     *

     * @return New {@link PropertyMap} with {@link Property} removed or {@code null} if not found.

     */

    public final synchronized PropertyMap deleteProperty(final Property property) {

        propertyChanged(property);

        PropertyMap newMap = checkHistory(property);

        final Object key = property.getKey();

        if (newMap == null && properties.containsKey(key)) {

            final PropertyHashMap newProperties = properties.immutableRemove(key);

            final boolean isSpill = property.isSpill();

            final int slot = property.getSlot();

            // If deleted property was last field or spill slot we can make it reusable by reducing field/slot count.

            // Otherwise mark it as free in free slots bitset.

            if (isSpill && slot >= 0 && slot == spillLength - 1) {

                newMap = deriveMap(newProperties, flags, fieldCount, spillLength - 1);

                newMap.freeSlots = freeSlots;

            } else if (!isSpill && slot >= 0 && slot == fieldCount - 1) {

                newMap = deriveMap(newProperties, flags, fieldCount - 1, spillLength);

                newMap.freeSlots = freeSlots;

            } else {

                newMap = deriveMap(newProperties, flags, fieldCount, spillLength);

                newMap.updateFreeSlots(property, null);

            }

            addToHistory(property, newMap);

        }

        return newMap;

    }

    /**

     * Replace an existing property with a new one.

     *

     * @param oldProperty Property to replace.

     * @param newProperty New {@link Property}.

     *

     * @return New {@link PropertyMap} with {@link Property} replaced.

     */

    public final PropertyMap replaceProperty(final Property oldProperty, final Property newProperty) {

        propertyChanged(oldProperty);

        /*

         * See ScriptObject.modifyProperty and ScriptObject.setUserAccessors methods.

         *

         * This replaceProperty method is called only for the following three cases:

         *

         *   1. To change flags OR TYPE of an old (cloned) property. We use the same spill slots.

         *   2. To change one UserAccessor property with another - user getter or setter changed via

         *      Object.defineProperty function. Again, same spill slots are re-used.

         *   3. Via ScriptObject.setUserAccessors method to set user getter and setter functions

         *      replacing the dummy AccessorProperty with null method handles (added during map init).

         *

         * In case (1) and case(2), the property type of old and new property is same. For case (3),

         * the old property is an AccessorProperty and the new one is a UserAccessorProperty property.

         */

        final boolean sameType = oldProperty.getClass() == newProperty.getClass();

        assert sameType ||

                oldProperty instanceof AccessorProperty &&

                newProperty instanceof UserAccessorProperty :

            "arbitrary replaceProperty attempted " + sameType + " oldProperty=" + oldProperty.getClass() + " newProperty=" + newProperty.getClass() + " [" + oldProperty.getLocalType() + " => " + newProperty.getLocalType() + "]";

        /*

         * spillLength remains same in case (1) and (2) because of slot reuse. Only for case (3), we need

         * to add spill count of the newly added UserAccessorProperty property.

         */

        final int newSpillLength = sameType ? spillLength : Math.max(spillLength, newProperty.getSlot() + 1);

        // Add replaces existing property.

        final PropertyHashMap newProperties = properties.immutableReplace(oldProperty, newProperty);

        final PropertyMap newMap = deriveMap(newProperties, flags, fieldCount, newSpillLength);

        if (!sameType) {

            newMap.updateFreeSlots(oldProperty, newProperty);

        }

        return newMap;

    }