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