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