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