1 /*
   2  * Copyright (c) 2010, 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.runtime;
  27 
  28 import static jdk.nashorn.internal.runtime.PropertyHashMap.EMPTY_HASHMAP;
  29 import static jdk.nashorn.internal.runtime.arrays.ArrayIndex.getArrayIndex;
  30 import static jdk.nashorn.internal.runtime.arrays.ArrayIndex.isValidArrayIndex;
  31 
  32 import java.io.IOException;
  33 import java.io.ObjectInputStream;
  34 import java.io.ObjectOutputStream;
  35 import java.io.Serializable;
  36 import java.lang.invoke.SwitchPoint;
  37 import java.lang.ref.Reference;
  38 import java.lang.ref.SoftReference;
  39 import java.lang.ref.WeakReference;
  40 import java.util.Arrays;
  41 import java.util.BitSet;
  42 import java.util.Collection;
  43 import java.util.HashMap;
  44 import java.util.Iterator;
  45 import java.util.NoSuchElementException;
  46 import java.util.WeakHashMap;
  47 import java.util.concurrent.atomic.LongAdder;
  48 import jdk.nashorn.internal.runtime.options.Options;
  49 import jdk.nashorn.internal.scripts.JO;
  50 
  51 /**
  52  * Map of object properties. The PropertyMap is the "template" for JavaScript object
  53  * layouts. It contains a map with prototype names as keys and {@link Property} instances
  54  * as values. A PropertyMap is typically passed to the {@link ScriptObject} constructor
  55  * to form the seed map for the ScriptObject.
  56  * <p>
  57  * All property maps are immutable. If a property is added, modified or removed, the mutator
  58  * will return a new map.
  59  */
  60 public class PropertyMap implements Iterable<Object>, Serializable {
  61     private static final int INITIAL_SOFT_REFERENCE_DERIVATION_LIMIT =
  62             Math.max(0, Options.getIntProperty("nashorn.propertyMap.softReferenceDerivationLimit", 32));
  63 
  64     /** Used for non extensible PropertyMaps, negative logic as the normal case is extensible. See {@link ScriptObject#preventExtensions()} */
  65     private static final int NOT_EXTENSIBLE         = 0b0000_0001;
  66     /** Does this map contain valid array keys? */
  67     private static final int CONTAINS_ARRAY_KEYS    = 0b0000_0010;
  68 
  69     /** Map status flags. */
  70     private final int flags;
  71 
  72     /** Map of properties. */
  73     private transient PropertyHashMap properties;
  74 
  75     /** Number of fields in use. */
  76     private final int fieldCount;
  77 
  78     /** Number of fields available. */
  79     private final int fieldMaximum;
  80 
  81     /** Length of spill in use. */
  82     private final int spillLength;
  83 
  84     /** Structure class name */
  85     private final String className;
  86 
  87     /**
  88      * Countdown of number of times this property map has been derived from another property map. When it
  89      * reaches zero, the property map will start using weak references instead of soft references to hold on
  90      * to its history elements.
  91      */
  92     private final int softReferenceDerivationLimit;
  93 
  94     /** A reference to the expected shared prototype property map. If this is set this
  95      * property map should only be used if it the same as the actual prototype map. */
  96     private transient SharedPropertyMap sharedProtoMap;
  97 
  98     /** {@link SwitchPoint}s for gets on inherited properties. */
  99     private transient HashMap<Object, SwitchPoint> protoSwitches;
 100 
 101     /** History of maps, used to limit map duplication. */
 102     private transient WeakHashMap<Property, Reference<PropertyMap>> history;
 103 
 104     /** History of prototypes, used to limit map duplication. */
 105     private transient WeakHashMap<ScriptObject, SoftReference<PropertyMap>> protoHistory;
 106 
 107     /** property listeners */
 108     private transient PropertyListeners listeners;
 109 
 110     private transient BitSet freeSlots;
 111 
 112     private static final long serialVersionUID = -7041836752008732533L;
 113 
 114     /**
 115      * Constructs a new property map.
 116      *
 117      * @param properties   A {@link PropertyHashMap} with initial contents.
 118      * @param fieldCount   Number of fields in use.
 119      * @param fieldMaximum Number of fields available.
 120      * @param spillLength  Number of spill slots used.
 121      */
 122     private PropertyMap(final PropertyHashMap properties, final int flags, final String className,
 123                         final int fieldCount, final int fieldMaximum, final int spillLength) {
 124         this.properties   = properties;
 125         this.className    = className;
 126         this.fieldCount   = fieldCount;
 127         this.fieldMaximum = fieldMaximum;
 128         this.spillLength  = spillLength;
 129         this.flags        = flags;
 130         this.softReferenceDerivationLimit = INITIAL_SOFT_REFERENCE_DERIVATION_LIMIT;
 131 
 132         if (Context.DEBUG) {
 133             count.increment();
 134         }
 135     }
 136 
 137     /**
 138      * Constructs a clone of {@code propertyMap} with changed properties, flags, or boundaries.
 139      *
 140      * @param propertyMap Existing property map.
 141      * @param properties  A {@link PropertyHashMap} with a new set of properties.
 142      */
 143     private PropertyMap(final PropertyMap propertyMap, final PropertyHashMap properties, final int flags, final int fieldCount, final int spillLength, final int softReferenceDerivationLimit) {
 144         this.properties   = properties;
 145         this.flags        = flags;
 146         this.spillLength  = spillLength;
 147         this.fieldCount   = fieldCount;
 148         this.fieldMaximum = propertyMap.fieldMaximum;
 149         this.className    = propertyMap.className;
 150         // We inherit the parent property listeners instance. It will be cloned when a new listener is added.
 151         this.listeners    = propertyMap.listeners;
 152         this.freeSlots    = propertyMap.freeSlots;
 153         this.sharedProtoMap = propertyMap.sharedProtoMap;
 154         this.softReferenceDerivationLimit = softReferenceDerivationLimit;
 155 
 156         if (Context.DEBUG) {
 157             count.increment();
 158             clonedCount.increment();
 159         }
 160     }
 161 
 162     /**
 163      * Constructs an exact clone of {@code propertyMap}.
 164      *
 165      * @param propertyMap Existing property map.
 166       */
 167     protected PropertyMap(final PropertyMap propertyMap) {
 168         this(propertyMap, propertyMap.properties, propertyMap.flags, propertyMap.fieldCount, propertyMap.spillLength, propertyMap.softReferenceDerivationLimit);
 169     }
 170 
 171     private void writeObject(final ObjectOutputStream out) throws IOException {
 172         out.defaultWriteObject();
 173         out.writeObject(properties.getProperties());
 174     }
 175 
 176     private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
 177         in.defaultReadObject();
 178 
 179         final Property[] props = (Property[]) in.readObject();
 180         this.properties = EMPTY_HASHMAP.immutableAdd(props);
 181 
 182         assert className != null;
 183         final Class<?> structure = Context.forStructureClass(className);
 184         for (final Property prop : props) {
 185             prop.initMethodHandles(structure);
 186         }
 187     }
 188 
 189     /**
 190      * Public property map allocator.
 191      *
 192      * <p>It is the caller's responsibility to make sure that {@code properties} does not contain
 193      * properties with keys that are valid array indices.</p>
 194      *
 195      * @param properties   Collection of initial properties.
 196      * @param className    class name
 197      * @param fieldCount   Number of fields in use.
 198      * @param fieldMaximum Number of fields available.
 199      * @param spillLength  Number of used spill slots.
 200      * @return New {@link PropertyMap}.
 201      */
 202     public static PropertyMap newMap(final Collection<Property> properties, final String className, final int fieldCount, final int fieldMaximum,  final int spillLength) {
 203         final PropertyHashMap newProperties = EMPTY_HASHMAP.immutableAdd(properties);
 204         return new PropertyMap(newProperties, 0, className, fieldCount, fieldMaximum, spillLength);
 205     }
 206 
 207     /**
 208      * Public property map allocator. Used by nasgen generated code.
 209      *
 210      * <p>It is the caller's responsibility to make sure that {@code properties} does not contain
 211      * properties with keys that are valid array indices.</p>
 212      *
 213      * @param properties Collection of initial properties.
 214      * @return New {@link PropertyMap}.
 215      */
 216     public static PropertyMap newMap(final Collection<Property> properties) {
 217         return properties == null || properties.isEmpty()? newMap() : newMap(properties, JO.class.getName(), 0, 0, 0);
 218     }
 219 
 220     /**
 221      * Return a sharable empty map for the given object class.
 222      * @param clazz the base object class
 223      * @return New empty {@link PropertyMap}.
 224      */
 225     public static PropertyMap newMap(final Class<? extends ScriptObject> clazz) {
 226         return new PropertyMap(EMPTY_HASHMAP, 0, clazz.getName(), 0, 0, 0);
 227     }
 228 
 229     /**
 230      * Return a sharable empty map.
 231      *
 232      * @return New empty {@link PropertyMap}.
 233      */
 234     public static PropertyMap newMap() {
 235         return newMap(JO.class);
 236     }
 237 
 238     /**
 239      * Return number of properties in the map.
 240      *
 241      * @return Number of properties.
 242      */
 243     public int size() {
 244         return properties.size();
 245     }
 246 
 247     /**
 248      * Get the number of listeners of this map
 249      *
 250      * @return the number of listeners
 251      */
 252     public int getListenerCount() {
 253         return listeners == null ? 0 : listeners.getListenerCount();
 254     }
 255 
 256     /**
 257      * Add {@code listenerMap} as a listener to this property map for the given {@code key}.
 258      *
 259      * @param key the property name
 260      * @param listenerMap the listener map
 261      */
 262     public void addListener(final String key, final PropertyMap listenerMap) {
 263         if (listenerMap != this) {
 264             // We need to clone listener instance when adding a new listener since we share
 265             // the listeners instance with our parent maps that don't need to see the new listener.
 266             listeners = PropertyListeners.addListener(listeners, key, listenerMap);
 267         }
 268     }
 269 
 270     /**
 271      * A new property is being added.
 272      *
 273      * @param property The new Property added.
 274      * @param isSelf was the property added to this map?
 275      */
 276     public void propertyAdded(final Property property, final boolean isSelf) {
 277         if (!isSelf) {
 278             invalidateProtoSwitchPoint(property.getKey());
 279         }
 280         if (listeners != null) {
 281             listeners.propertyAdded(property);
 282         }
 283     }
 284 
 285     /**
 286      * An existing property is being deleted.
 287      *
 288      * @param property The property being deleted.
 289      * @param isSelf was the property deleted from this map?
 290      */
 291     public void propertyDeleted(final Property property, final boolean isSelf) {
 292         if (!isSelf) {
 293             invalidateProtoSwitchPoint(property.getKey());
 294         }
 295         if (listeners != null) {
 296             listeners.propertyDeleted(property);
 297         }
 298     }
 299 
 300     /**
 301      * An existing property is being redefined.
 302      *
 303      * @param oldProperty The old property
 304      * @param newProperty The new property
 305      * @param isSelf was the property modified on this map?
 306      */
 307     public void propertyModified(final Property oldProperty, final Property newProperty, final boolean isSelf) {
 308         if (!isSelf) {
 309             invalidateProtoSwitchPoint(oldProperty.getKey());
 310         }
 311         if (listeners != null) {
 312             listeners.propertyModified(oldProperty, newProperty);
 313         }
 314     }
 315 
 316     /**
 317      * The prototype of an object associated with this {@link PropertyMap} is changed.
 318      *
 319      * @param isSelf was the prototype changed on the object using this map?
 320      */
 321     public void protoChanged(final boolean isSelf) {
 322         if (!isSelf) {
 323             invalidateAllProtoSwitchPoints();
 324         } else if (sharedProtoMap != null) {
 325             sharedProtoMap.invalidateSwitchPoint();
 326         }
 327         if (listeners != null) {
 328             listeners.protoChanged();
 329         }
 330     }
 331 
 332     /**
 333      * Return a SwitchPoint used to track changes of a property in a prototype.
 334      *
 335      * @param key Property key.
 336      * @return A shared {@link SwitchPoint} for the property.
 337      */
 338     public synchronized SwitchPoint getSwitchPoint(final String key) {
 339         if (protoSwitches == null) {
 340             protoSwitches = new HashMap<>();
 341         }
 342 
 343         SwitchPoint switchPoint = protoSwitches.get(key);
 344         if (switchPoint == null) {
 345             switchPoint = new SwitchPoint();
 346             protoSwitches.put(key, switchPoint);
 347         }
 348 
 349         return switchPoint;
 350     }
 351 
 352     /**
 353      * Indicate that a prototype property has changed.
 354      *
 355      * @param key {@link Property} key to invalidate.
 356      */
 357     synchronized void invalidateProtoSwitchPoint(final Object key) {
 358         if (protoSwitches != null) {
 359             final SwitchPoint sp = protoSwitches.get(key);
 360             if (sp != null) {
 361                 protoSwitches.remove(key);
 362                 if (Context.DEBUG) {
 363                     protoInvalidations.increment();
 364                 }
 365                 SwitchPoint.invalidateAll(new SwitchPoint[]{sp});
 366             }
 367         }
 368     }
 369 
 370     /**
 371      * Indicate that proto itself has changed in hierarchy somewhere.
 372      */
 373     synchronized void invalidateAllProtoSwitchPoints() {
 374         if (protoSwitches != null) {
 375             final int size = protoSwitches.size();
 376             if (size > 0) {
 377                 if (Context.DEBUG) {
 378                     protoInvalidations.add(size);
 379                 }
 380                 SwitchPoint.invalidateAll(protoSwitches.values().toArray(new SwitchPoint[0]));
 381                 protoSwitches.clear();
 382             }
 383         }
 384     }
 385 
 386     /**
 387      * Add a property to the map, re-binding its getters and setters,
 388      * if available, to a given receiver. This is typically the global scope. See
 389      * {@link ScriptObject#addBoundProperties(ScriptObject)}
 390      *
 391      * @param property {@link Property} being added.
 392      * @param bindTo   Object to bind to.
 393      *
 394      * @return New {@link PropertyMap} with {@link Property} added.
 395      */
 396     PropertyMap addPropertyBind(final AccessorProperty property, final Object bindTo) {
 397         // We must not store bound property in the history as bound properties can't be reused.
 398         return addPropertyNoHistory(new AccessorProperty(property, bindTo));
 399     }
 400 
 401     // Get a logical slot index for a property, with spill slot 0 starting at fieldMaximum.
 402     private int logicalSlotIndex(final Property property) {
 403         final int slot = property.getSlot();
 404         if (slot < 0) {
 405             return -1;
 406         }
 407         return property.isSpill() ? slot + fieldMaximum : slot;
 408     }
 409 
 410     private int newSpillLength(final Property newProperty) {
 411         return newProperty.isSpill() ? Math.max(spillLength, newProperty.getSlot() + 1) : spillLength;
 412     }
 413 
 414     private int newFieldCount(final Property newProperty) {
 415         return !newProperty.isSpill() ? Math.max(fieldCount, newProperty.getSlot() + 1) : fieldCount;
 416     }
 417 
 418     private int newFlags(final Property newProperty) {
 419         return isValidArrayIndex(getArrayIndex(newProperty.getKey())) ? flags | CONTAINS_ARRAY_KEYS : flags;
 420     }
 421 
 422     // Update the free slots bitmap for a property that has been deleted and/or added. This method is not synchronized
 423     // as it is always invoked on a newly created instance.
 424     private void updateFreeSlots(final Property oldProperty, final Property newProperty) {
 425         // Free slots bitset is possibly shared with parent map, so we must clone it before making modifications.
 426         boolean freeSlotsCloned = false;
 427         if (oldProperty != null) {
 428             final int slotIndex = logicalSlotIndex(oldProperty);
 429             if (slotIndex >= 0) {
 430                 final BitSet newFreeSlots = freeSlots == null ? new BitSet() : (BitSet)freeSlots.clone();
 431                 assert !newFreeSlots.get(slotIndex);
 432                 newFreeSlots.set(slotIndex);
 433                 freeSlots = newFreeSlots;
 434                 freeSlotsCloned = true;
 435             }
 436         }
 437         if (freeSlots != null && newProperty != null) {
 438             final int slotIndex = logicalSlotIndex(newProperty);
 439             if (slotIndex > -1 && freeSlots.get(slotIndex)) {
 440                 final BitSet newFreeSlots = freeSlotsCloned ? freeSlots : ((BitSet)freeSlots.clone());
 441                 newFreeSlots.clear(slotIndex);
 442                 freeSlots = newFreeSlots.isEmpty() ? null : newFreeSlots;
 443             }
 444         }
 445     }
 446 
 447     /**
 448      * Add a property to the map without adding it to the history. This should be used for properties that
 449      * can't be shared such as bound properties, or properties that are expected to be added only once.
 450      *
 451      * @param property {@link Property} being added.
 452      * @return New {@link PropertyMap} with {@link Property} added.
 453      */
 454     public final PropertyMap addPropertyNoHistory(final Property property) {
 455         propertyAdded(property, true);
 456         return addPropertyInternal(property);
 457     }
 458 
 459     /**
 460      * Add a property to the map.  Cloning or using an existing map if available.
 461      *
 462      * @param property {@link Property} being added.
 463      *
 464      * @return New {@link PropertyMap} with {@link Property} added.
 465      */
 466     public final synchronized PropertyMap addProperty(final Property property) {
 467         propertyAdded(property, true);
 468         PropertyMap newMap = checkHistory(property);
 469 
 470         if (newMap == null) {
 471             newMap = addPropertyInternal(property);
 472             addToHistory(property, newMap);
 473         }
 474 
 475         return newMap;
 476     }
 477 
 478     private PropertyMap deriveMap(final PropertyHashMap newProperties, final int newFlags, final int newFieldCount, final int newSpillLength) {
 479         return new PropertyMap(this, newProperties, newFlags, newFieldCount, newSpillLength, softReferenceDerivationLimit == 0 ? 0 : softReferenceDerivationLimit - 1);
 480     }
 481 
 482     private PropertyMap addPropertyInternal(final Property property) {
 483         final PropertyHashMap newProperties = properties.immutableAdd(property);
 484         final PropertyMap newMap = deriveMap(newProperties, newFlags(property), newFieldCount(property), newSpillLength(property));
 485         newMap.updateFreeSlots(null, property);
 486         return newMap;
 487     }
 488 
 489     /**
 490      * Remove a property from a map. Cloning or using an existing map if available.
 491      *
 492      * @param property {@link Property} being removed.
 493      *
 494      * @return New {@link PropertyMap} with {@link Property} removed or {@code null} if not found.
 495      */
 496     public final synchronized PropertyMap deleteProperty(final Property property) {
 497         propertyDeleted(property, true);
 498         PropertyMap newMap = checkHistory(property);
 499         final Object key = property.getKey();
 500 
 501         if (newMap == null && properties.containsKey(key)) {
 502             final PropertyHashMap newProperties = properties.immutableRemove(key);
 503             final boolean isSpill = property.isSpill();
 504             final int slot = property.getSlot();
 505             // If deleted property was last field or spill slot we can make it reusable by reducing field/slot count.
 506             // Otherwise mark it as free in free slots bitset.
 507             if (isSpill && slot >= 0 && slot == spillLength - 1) {
 508                 newMap = deriveMap(newProperties, flags, fieldCount, spillLength - 1);
 509                 newMap.freeSlots = freeSlots;
 510             } else if (!isSpill && slot >= 0 && slot == fieldCount - 1) {
 511                 newMap = deriveMap(newProperties, flags, fieldCount - 1, spillLength);
 512                 newMap.freeSlots = freeSlots;
 513             } else {
 514                 newMap = deriveMap(newProperties, flags, fieldCount, spillLength);
 515                 newMap.updateFreeSlots(property, null);
 516             }
 517             addToHistory(property, newMap);
 518         }
 519 
 520         return newMap;
 521     }
 522 
 523     /**
 524      * Replace an existing property with a new one.
 525      *
 526      * @param oldProperty Property to replace.
 527      * @param newProperty New {@link Property}.
 528      *
 529      * @return New {@link PropertyMap} with {@link Property} replaced.
 530      */
 531     public final PropertyMap replaceProperty(final Property oldProperty, final Property newProperty) {
 532         propertyModified(oldProperty, newProperty, true);
 533         /*
 534          * See ScriptObject.modifyProperty and ScriptObject.setUserAccessors methods.
 535          *
 536          * This replaceProperty method is called only for the following three cases:
 537          *
 538          *   1. To change flags OR TYPE of an old (cloned) property. We use the same spill slots.
 539          *   2. To change one UserAccessor property with another - user getter or setter changed via
 540          *      Object.defineProperty function. Again, same spill slots are re-used.
 541          *   3. Via ScriptObject.setUserAccessors method to set user getter and setter functions
 542          *      replacing the dummy AccessorProperty with null method handles (added during map init).
 543          *
 544          * In case (1) and case(2), the property type of old and new property is same. For case (3),
 545          * the old property is an AccessorProperty and the new one is a UserAccessorProperty property.
 546          */
 547 
 548         final boolean sameType = oldProperty.getClass() == newProperty.getClass();
 549         assert sameType ||
 550                 oldProperty instanceof AccessorProperty &&
 551                 newProperty instanceof UserAccessorProperty :
 552             "arbitrary replaceProperty attempted " + sameType + " oldProperty=" + oldProperty.getClass() + " newProperty=" + newProperty.getClass() + " [" + oldProperty.getLocalType() + " => " + newProperty.getLocalType() + "]";
 553 
 554         /*
 555          * spillLength remains same in case (1) and (2) because of slot reuse. Only for case (3), we need
 556          * to add spill count of the newly added UserAccessorProperty property.
 557          */
 558         final int newSpillLength = sameType ? spillLength : Math.max(spillLength, newProperty.getSlot() + 1);
 559 
 560         // Add replaces existing property.
 561         final PropertyHashMap newProperties = properties.immutableReplace(oldProperty, newProperty);
 562         final PropertyMap newMap = deriveMap(newProperties, flags, fieldCount, newSpillLength);
 563 
 564         if (!sameType) {
 565             newMap.updateFreeSlots(oldProperty, newProperty);
 566         }
 567         return newMap;
 568     }
 569 
 570     /**
 571      * Make a new UserAccessorProperty property. getter and setter functions are stored in
 572      * this ScriptObject and slot values are used in property object. Note that slots
 573      * are assigned speculatively and should be added to map before adding other
 574      * properties.
 575      *
 576      * @param key the property name
 577      * @param propertyFlags attribute flags of the property
 578      * @return the newly created UserAccessorProperty
 579      */
 580     public final UserAccessorProperty newUserAccessors(final Object key, final int propertyFlags) {
 581         return new UserAccessorProperty(key, propertyFlags, getFreeSpillSlot());
 582     }
 583 
 584     /**
 585      * Find a property in the map.
 586      *
 587      * @param key Key to search for.
 588      *
 589      * @return {@link Property} matching key.
 590      */
 591     public final Property findProperty(final Object key) {
 592         return properties.find(key);
 593     }
 594 
 595     /**
 596      * Adds all map properties from another map.
 597      *
 598      * @param other The source of properties.
 599      *
 600      * @return New {@link PropertyMap} with added properties.
 601      */
 602     public final PropertyMap addAll(final PropertyMap other) {
 603         assert this != other : "adding property map to itself";
 604         final Property[] otherProperties = other.properties.getProperties();
 605         final PropertyHashMap newProperties = properties.immutableAdd(otherProperties);
 606 
 607         final PropertyMap newMap = deriveMap(newProperties, flags, fieldCount, spillLength);
 608         for (final Property property : otherProperties) {
 609             // This method is only safe to use with non-slotted, native getter/setter properties
 610             assert property.getSlot() == -1;
 611             assert !(isValidArrayIndex(getArrayIndex(property.getKey())));
 612         }
 613 
 614         return newMap;
 615     }
 616 
 617     /**
 618      * Return an array of all properties.
 619      *
 620      * @return Properties as an array.
 621      */
 622     public final Property[] getProperties() {
 623         return properties.getProperties();
 624     }
 625 
 626     /**
 627      * Return the name of the class of objects using this property map.
 628      *
 629      * @return class name of owner objects.
 630      */
 631     public final String getClassName() {
 632         return className;
 633     }
 634 
 635     /**
 636      * Prevents the map from having additional properties.
 637      *
 638      * @return New map with {@link #NOT_EXTENSIBLE} flag set.
 639      */
 640     PropertyMap preventExtensions() {
 641         return deriveMap(properties, flags | NOT_EXTENSIBLE, fieldCount, spillLength);
 642     }
 643 
 644     /**
 645      * Prevents properties in map from being modified.
 646      *
 647      * @return New map with {@link #NOT_EXTENSIBLE} flag set and properties with
 648      * {@link Property#NOT_CONFIGURABLE} set.
 649      */
 650     PropertyMap seal() {
 651         PropertyHashMap newProperties = EMPTY_HASHMAP;
 652 
 653         for (final Property oldProperty :  properties.getProperties()) {
 654             newProperties = newProperties.immutableAdd(oldProperty.addFlags(Property.NOT_CONFIGURABLE));
 655         }
 656 
 657         return deriveMap(newProperties, flags | NOT_EXTENSIBLE, fieldCount, spillLength);
 658     }
 659 
 660     /**
 661      * Prevents properties in map from being modified or written to.
 662      *
 663      * @return New map with {@link #NOT_EXTENSIBLE} flag set and properties with
 664      * {@link Property#NOT_CONFIGURABLE} and {@link Property#NOT_WRITABLE} set.
 665      */
 666     PropertyMap freeze() {
 667         PropertyHashMap newProperties = EMPTY_HASHMAP;
 668 
 669         for (final Property oldProperty : properties.getProperties()) {
 670             int propertyFlags = Property.NOT_CONFIGURABLE;
 671 
 672             if (!(oldProperty instanceof UserAccessorProperty)) {
 673                 propertyFlags |= Property.NOT_WRITABLE;
 674             }
 675 
 676             newProperties = newProperties.immutableAdd(oldProperty.addFlags(propertyFlags));
 677         }
 678 
 679         return deriveMap(newProperties, flags | NOT_EXTENSIBLE, fieldCount, spillLength);
 680     }
 681 
 682     /**
 683      * Check for any configurable properties.
 684      *
 685      * @return {@code true} if any configurable.
 686      */
 687     private boolean anyConfigurable() {
 688         for (final Property property : properties.getProperties()) {
 689             if (property.isConfigurable()) {
 690                return true;
 691             }
 692         }
 693 
 694         return false;
 695     }
 696 
 697     /**
 698      * Check if all properties are frozen.
 699      *
 700      * @return {@code true} if all are frozen.
 701      */
 702     private boolean allFrozen() {
 703         for (final Property property : properties.getProperties()) {
 704             // check if it is a data descriptor
 705             if (!property.isAccessorProperty() && property.isWritable()) {
 706                 return false;
 707             }
 708             if (property.isConfigurable()) {
 709                return false;
 710             }
 711         }
 712 
 713         return true;
 714     }
 715 
 716     /**
 717      * Check prototype history for an existing property map with specified prototype.
 718      *
 719      * @param proto New prototype object.
 720      *
 721      * @return Existing {@link PropertyMap} or {@code null} if not found.
 722      */
 723     private PropertyMap checkProtoHistory(final ScriptObject proto) {
 724         final PropertyMap cachedMap;
 725         if (protoHistory != null) {
 726             final SoftReference<PropertyMap> weakMap = protoHistory.get(proto);
 727             cachedMap = (weakMap != null ? weakMap.get() : null);
 728         } else {
 729             cachedMap = null;
 730         }
 731 
 732         if (Context.DEBUG && cachedMap != null) {
 733             protoHistoryHit.increment();
 734         }
 735 
 736         return cachedMap;
 737     }
 738 
 739     /**
 740      * Add a map to the prototype history.
 741      *
 742      * @param newProto Prototype to add (key.)
 743      * @param newMap   {@link PropertyMap} associated with prototype.
 744      */
 745     private void addToProtoHistory(final ScriptObject newProto, final PropertyMap newMap) {
 746         if (protoHistory == null) {
 747             protoHistory = new WeakHashMap<>();
 748         }
 749 
 750         protoHistory.put(newProto, new SoftReference<>(newMap));
 751     }
 752 
 753     /**
 754      * Track the modification of the map.
 755      *
 756      * @param property Mapping property.
 757      * @param newMap   Modified {@link PropertyMap}.
 758      */
 759     private void addToHistory(final Property property, final PropertyMap newMap) {
 760         if (history == null) {
 761             history = new WeakHashMap<>();
 762         }
 763 
 764         history.put(property, softReferenceDerivationLimit == 0 ? new WeakReference<>(newMap) : new SoftReference<>(newMap));
 765     }
 766 
 767     /**
 768      * Check the history for a map that already has the given property added.
 769      *
 770      * @param property {@link Property} to add.
 771      *
 772      * @return Existing map or {@code null} if not found.
 773      */
 774     private PropertyMap checkHistory(final Property property) {
 775 
 776         if (history != null) {
 777             final Reference<PropertyMap> ref = history.get(property);
 778             final PropertyMap historicMap = ref == null ? null : ref.get();
 779 
 780             if (historicMap != null) {
 781                 if (Context.DEBUG) {
 782                     historyHit.increment();
 783                 }
 784 
 785                 return historicMap;
 786             }
 787         }
 788 
 789         return null;
 790     }
 791 
 792     /**
 793      * Returns true if the two maps have identical properties in the same order, but allows the properties to differ in
 794      * their types. This method is mostly useful for tests.
 795      * @param otherMap the other map
 796      * @return true if this map has identical properties in the same order as the other map, allowing the properties to
 797      * differ in type.
 798      */
 799     public boolean equalsWithoutType(final PropertyMap otherMap) {
 800         if (properties.size() != otherMap.properties.size()) {
 801             return false;
 802         }
 803 
 804         final Iterator<Property> iter      = properties.values().iterator();
 805         final Iterator<Property> otherIter = otherMap.properties.values().iterator();
 806 
 807         while (iter.hasNext() && otherIter.hasNext()) {
 808             if (!iter.next().equalsWithoutType(otherIter.next())) {
 809                 return false;
 810             }
 811         }
 812 
 813         return true;
 814     }
 815 
 816     @Override
 817     public String toString() {
 818         final StringBuilder sb = new StringBuilder();
 819 
 820         sb.append(Debug.id(this));
 821         sb.append(" = {\n");
 822 
 823         for (final Property property : getProperties()) {
 824             sb.append('\t');
 825             sb.append(property);
 826             sb.append('\n');
 827         }
 828 
 829         sb.append('}');
 830 
 831         return sb.toString();
 832     }
 833 
 834     @Override
 835     public Iterator<Object> iterator() {
 836         return new PropertyMapIterator(this);
 837     }
 838 
 839     /**
 840      * Check if this map contains properties with valid array keys
 841      *
 842      * @return {@code true} if this map contains properties with valid array keys
 843      */
 844     public final boolean containsArrayKeys() {
 845         return (flags & CONTAINS_ARRAY_KEYS) != 0;
 846     }
 847 
 848     /**
 849      * Test to see if {@link PropertyMap} is extensible.
 850      *
 851      * @return {@code true} if {@link PropertyMap} can be added to.
 852      */
 853     boolean isExtensible() {
 854         return (flags & NOT_EXTENSIBLE) == 0;
 855     }
 856 
 857     /**
 858      * Test to see if {@link PropertyMap} is not extensible or any properties
 859      * can not be modified.
 860      *
 861      * @return {@code true} if {@link PropertyMap} is sealed.
 862      */
 863     boolean isSealed() {
 864         return !isExtensible() && !anyConfigurable();
 865     }
 866 
 867     /**
 868      * Test to see if {@link PropertyMap} is not extensible or all properties
 869      * can not be modified.
 870      *
 871      * @return {@code true} if {@link PropertyMap} is frozen.
 872      */
 873     boolean isFrozen() {
 874         return !isExtensible() && allFrozen();
 875     }
 876 
 877     /**
 878      * Return a free field slot for this map, or {@code -1} if none is available.
 879      *
 880      * @return free field slot or -1
 881      */
 882     int getFreeFieldSlot() {
 883         if (freeSlots != null) {
 884             final int freeSlot = freeSlots.nextSetBit(0);
 885             if (freeSlot > -1 && freeSlot < fieldMaximum) {
 886                 return freeSlot;
 887             }
 888         }
 889         if (fieldCount < fieldMaximum) {
 890             return fieldCount;
 891         }
 892         return -1;
 893     }
 894 
 895     /**
 896      * Get a free spill slot for this map.
 897      *
 898      * @return free spill slot
 899      */
 900     int getFreeSpillSlot() {
 901         if (freeSlots != null) {
 902             final int freeSlot = freeSlots.nextSetBit(fieldMaximum);
 903             if (freeSlot > -1) {
 904                 return freeSlot - fieldMaximum;
 905             }
 906         }
 907         return spillLength;
 908     }
 909 
 910     /**
 911      * Return a property map with the same layout that is associated with the new prototype object.
 912      *
 913      * @param newProto New prototype object to replace oldProto.
 914      * @return New {@link PropertyMap} with prototype changed.
 915      */
 916     public synchronized PropertyMap changeProto(final ScriptObject newProto) {
 917         final PropertyMap nextMap = checkProtoHistory(newProto);
 918         if (nextMap != null) {
 919             return nextMap;
 920         }
 921 
 922         if (Context.DEBUG) {
 923             setProtoNewMapCount.increment();
 924         }
 925 
 926         final PropertyMap newMap = makeUnsharedCopy();
 927         addToProtoHistory(newProto, newMap);
 928 
 929         return newMap;
 930     }
 931 
 932     /**
 933      * Make a copy of this property map with the shared prototype field set to null. Note that this is
 934      * only necessary for shared maps of top-level objects. Shared prototype maps represented by
 935      * {@link SharedPropertyMap} are automatically converted to plain property maps when they evolve.
 936      *
 937      * @return a copy with the shared proto map unset
 938      */
 939     PropertyMap makeUnsharedCopy() {
 940         final PropertyMap newMap = new PropertyMap(this);
 941         newMap.sharedProtoMap = null;
 942         return newMap;
 943     }
 944 
 945     /**
 946      * Set a reference to the expected parent prototype map. This is used for class-like
 947      * structures where we only want to use a top-level property map if all of the
 948      * prototype property maps have not been modified.
 949      *
 950      * @param protoMap weak reference to the prototype property map
 951      */
 952     void setSharedProtoMap(final SharedPropertyMap protoMap) {
 953         sharedProtoMap = protoMap;
 954     }
 955 
 956     /**
 957      * Get the expected prototype property map if it is known, or null.
 958      *
 959      * @return parent map or null
 960      */
 961     public PropertyMap getSharedProtoMap() {
 962         return sharedProtoMap;
 963     }
 964 
 965     /**
 966      * Returns {@code true} if this map has been used as a shared prototype map (i.e. as a prototype
 967      * for a JavaScript constructor function) and has not had properties added, deleted or replaced since then.
 968      * @return true if this is a valid shared prototype map
 969      */
 970     boolean isValidSharedProtoMap() {
 971         return false;
 972     }
 973 
 974     /**
 975      * Returns the shared prototype switch point, or null if this is not a shared prototype map.
 976      * @return the shared prototype switch point, or null
 977      */
 978     SwitchPoint getSharedProtoSwitchPoint() {
 979         return null;
 980     }
 981 
 982     /**
 983      * Return true if this map has a shared prototype map which has either been invalidated or does
 984      * not match the map of {@code proto}.
 985      * @param prototype the prototype object
 986      * @return true if this is an invalid shared map for {@code prototype}
 987      */
 988     boolean isInvalidSharedMapFor(final ScriptObject prototype) {
 989         return sharedProtoMap != null
 990                 && (!sharedProtoMap.isValidSharedProtoMap() || prototype == null || sharedProtoMap != prototype.getMap());
 991     }
 992 
 993     /**
 994      * {@link PropertyMap} iterator.
 995      */
 996     private static class PropertyMapIterator implements Iterator<Object> {
 997         /** Property iterator. */
 998         final Iterator<Property> iter;
 999 
1000         /** Current Property. */
1001         Property property;
1002 
1003         /**
1004          * Constructor.
1005          *
1006          * @param propertyMap {@link PropertyMap} to iterate over.
1007          */
1008         PropertyMapIterator(final PropertyMap propertyMap) {
1009             iter = Arrays.asList(propertyMap.properties.getProperties()).iterator();
1010             property = iter.hasNext() ? iter.next() : null;
1011             skipNotEnumerable();
1012         }
1013 
1014         /**
1015          * Ignore properties that are not enumerable.
1016          */
1017         private void skipNotEnumerable() {
1018             while (property != null && !property.isEnumerable()) {
1019                 property = iter.hasNext() ? iter.next() : null;
1020             }
1021         }
1022 
1023         @Override
1024         public boolean hasNext() {
1025             return property != null;
1026         }
1027 
1028         @Override
1029         public Object next() {
1030             if (property == null) {
1031                 throw new NoSuchElementException();
1032             }
1033 
1034             final Object key = property.getKey();
1035             property = iter.hasNext() ? iter.next() : null;
1036             skipNotEnumerable();
1037 
1038             return key;
1039         }
1040 
1041         @Override
1042         public void remove() {
1043             throw new UnsupportedOperationException("remove");
1044         }
1045     }
1046 
1047     /*
1048      * Debugging and statistics.
1049      */
1050 
1051     /**
1052      * Debug helper function that returns the diff of two property maps, only
1053      * displaying the information that is different and in which map it exists
1054      * compared to the other map. Can be used to e.g. debug map guards and
1055      * investigate why they fail, causing relink
1056      *
1057      * @param map0 the first property map
1058      * @param map1 the second property map
1059      *
1060      * @return property map diff as string
1061      */
1062     public static String diff(final PropertyMap map0, final PropertyMap map1) {
1063         final StringBuilder sb = new StringBuilder();
1064 
1065         if (map0 != map1) {
1066            sb.append(">>> START: Map diff");
1067            boolean found = false;
1068 
1069            for (final Property p : map0.getProperties()) {
1070                final Property p2 = map1.findProperty(p.getKey());
1071                if (p2 == null) {
1072                    sb.append("FIRST ONLY : [").append(p).append("]");
1073                    found = true;
1074                } else if (p2 != p) {
1075                    sb.append("DIFFERENT  : [").append(p).append("] != [").append(p2).append("]");
1076                    found = true;
1077                }
1078            }
1079 
1080            for (final Property p2 : map1.getProperties()) {
1081                final Property p1 = map0.findProperty(p2.getKey());
1082                if (p1 == null) {
1083                    sb.append("SECOND ONLY: [").append(p2).append("]");
1084                    found = true;
1085                }
1086            }
1087 
1088            //assert found;
1089 
1090            if (!found) {
1091                 sb.append(map0).
1092                     append("!=").
1093                     append(map1);
1094            }
1095 
1096            sb.append("<<< END: Map diff\n");
1097         }
1098 
1099         return sb.toString();
1100     }
1101 
1102     // counters updated only in debug mode
1103     private static LongAdder count;
1104     private static LongAdder clonedCount;
1105     private static LongAdder historyHit;
1106     private static LongAdder protoInvalidations;
1107     private static LongAdder protoHistoryHit;
1108     private static LongAdder setProtoNewMapCount;
1109     static {
1110         if (Context.DEBUG) {
1111             count = new LongAdder();
1112             clonedCount = new LongAdder();
1113             historyHit = new LongAdder();
1114             protoInvalidations = new LongAdder();
1115             protoHistoryHit = new LongAdder();
1116             setProtoNewMapCount = new LongAdder();
1117         }
1118     }
1119 
1120     /**
1121      * @return Total number of maps.
1122      */
1123     public static long getCount() {
1124         return count.longValue();
1125     }
1126 
1127     /**
1128      * @return The number of maps that were cloned.
1129      */
1130     public static long getClonedCount() {
1131         return clonedCount.longValue();
1132     }
1133 
1134     /**
1135      * @return The number of times history was successfully used.
1136      */
1137     public static long getHistoryHit() {
1138         return historyHit.longValue();
1139     }
1140 
1141     /**
1142      * @return The number of times prototype changes caused invalidation.
1143      */
1144     public static long getProtoInvalidations() {
1145         return protoInvalidations.longValue();
1146     }
1147 
1148     /**
1149      * @return The number of times proto history was successfully used.
1150      */
1151     public static long getProtoHistoryHit() {
1152         return protoHistoryHit.longValue();
1153     }
1154 
1155     /**
1156      * @return The number of times prototypes were modified.
1157      */
1158     public static long getSetProtoNewMapCount() {
1159         return setProtoNewMapCount.longValue();
1160     }
1161 }