Mercurial > hg > graal-compiler
comparison graal/com.oracle.truffle.object/src/com/oracle/truffle/object/ShapeImpl.java @ 18408:2c3666f44855
Truffle: initial commit of object API implementation
author | Andreas Woess <andreas.woess@jku.at> |
---|---|
date | Tue, 18 Nov 2014 23:19:43 +0100 |
parents | |
children | b3b241bbbbdb |
comparison
equal
deleted
inserted
replaced
18407:f439fdb137a3 | 18408:2c3666f44855 |
---|---|
1 /* | |
2 * Copyright (c) 2012, 2014, 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. | |
8 * | |
9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
12 * version 2 for more details (a copy is included in the LICENSE file that | |
13 * accompanied this code). | |
14 * | |
15 * You should have received a copy of the GNU General Public License version | |
16 * 2 along with this work; if not, write to the Free Software Foundation, | |
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
18 * | |
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
20 * or visit www.oracle.com if you need additional information or have any | |
21 * questions. | |
22 */ | |
23 package com.oracle.truffle.object; | |
24 | |
25 import java.util.*; | |
26 | |
27 import com.oracle.truffle.api.*; | |
28 import com.oracle.truffle.api.CompilerDirectives.CompilationFinal; | |
29 import com.oracle.truffle.api.CompilerDirectives.TruffleBoundary; | |
30 import com.oracle.truffle.api.nodes.*; | |
31 import com.oracle.truffle.api.object.*; | |
32 import com.oracle.truffle.object.LocationImpl.InternalLongLocation; | |
33 import com.oracle.truffle.object.Locations.ConstantLocation; | |
34 import com.oracle.truffle.object.Locations.DeclaredDualLocation; | |
35 import com.oracle.truffle.object.Locations.DeclaredLocation; | |
36 import com.oracle.truffle.object.Locations.DualLocation; | |
37 import com.oracle.truffle.object.Locations.ValueLocation; | |
38 import com.oracle.truffle.object.Transition.AddTransition; | |
39 import com.oracle.truffle.object.Transition.OperationsTransition; | |
40 import com.oracle.truffle.object.Transition.PropertyTransition; | |
41 import com.oracle.truffle.object.Transition.RemoveTransition; | |
42 | |
43 /** | |
44 * Shape objects create a mapping of Property objects to indexes. The mapping of those indexes to an | |
45 * actual store is not part of Shape's role, but JSObject's. Shapes are immutable; adding or | |
46 * deleting a property yields a new Shape which links to the old one. This allows inline caching to | |
47 * simply check the identity of an object's Shape to determine if the cache is valid. There is one | |
48 * exception to this immutability, the transition map, but that is used simply to assure that an | |
49 * identical series of property additions and deletions will yield the same Shape object. | |
50 * | |
51 * @see DynamicObject | |
52 * @see Property | |
53 * @see Locations | |
54 */ | |
55 public abstract class ShapeImpl extends Shape { | |
56 private final int id; | |
57 | |
58 protected final LayoutImpl layout; | |
59 protected final ObjectType objectType; | |
60 protected final ShapeImpl parent; | |
61 protected final PropertyMap propertyMap; | |
62 | |
63 private final Object extraData; | |
64 private final Object sharedData; | |
65 private final ShapeImpl root; | |
66 | |
67 protected final int objectArraySize; | |
68 protected final int objectArrayCapacity; | |
69 protected final int objectFieldSize; | |
70 protected final int primitiveFieldSize; | |
71 protected final int primitiveArraySize; | |
72 protected final int primitiveArrayCapacity; | |
73 protected final boolean hasPrimitiveArray; | |
74 | |
75 protected final int depth; | |
76 protected final int propertyCount; | |
77 protected Property[] propertyArray; | |
78 | |
79 protected final Assumption validAssumption; | |
80 protected final Assumption leafAssumption; | |
81 | |
82 /** | |
83 * Shape transition map; lazily initialized. | |
84 * | |
85 * @see #getTransitionMapForRead() | |
86 * @see #getTransitionMapForWrite() | |
87 */ | |
88 private HashMap<Transition, ShapeImpl> transitionMap; | |
89 | |
90 /** | |
91 * Private constructor. | |
92 * | |
93 * @see #ShapeImpl(Layout, ShapeImpl, ObjectType, Object, PropertyMap, BaseAllocator, int) | |
94 */ | |
95 private ShapeImpl(Layout layout, ShapeImpl parent, ObjectType operations, Object sharedData, PropertyMap propertyMap, int objectArraySize, int objectFieldSize, int primitiveFieldSize, | |
96 int primitiveArraySize, boolean hasPrimitiveArray, int id) { | |
97 this.layout = (LayoutImpl) layout; | |
98 this.objectType = Objects.requireNonNull(operations); | |
99 this.propertyMap = Objects.requireNonNull(propertyMap); | |
100 this.root = parent != null ? parent.getRoot() : this; | |
101 this.parent = parent; | |
102 this.objectArraySize = objectArraySize; | |
103 this.objectArrayCapacity = capacityFromSize(objectArraySize); | |
104 this.objectFieldSize = objectFieldSize; | |
105 this.primitiveFieldSize = primitiveFieldSize; | |
106 this.primitiveArraySize = primitiveArraySize; | |
107 this.primitiveArrayCapacity = capacityFromSize(primitiveArraySize); | |
108 this.hasPrimitiveArray = hasPrimitiveArray; | |
109 | |
110 if (parent != null) { | |
111 this.propertyCount = makePropertyCount(parent, propertyMap); | |
112 this.propertyArray = makePropertiesList(parent, propertyMap); | |
113 this.depth = parent.depth + 1; | |
114 } else { | |
115 this.propertyCount = 0; | |
116 this.propertyArray = null; | |
117 this.depth = 0; | |
118 } | |
119 | |
120 this.validAssumption = createValidAssumption(); | |
121 this.leafAssumption = createLeafAssumption(); | |
122 | |
123 this.id = id; | |
124 shapeCount.inc(); | |
125 | |
126 this.sharedData = sharedData; | |
127 this.extraData = operations.createShapeData(this); | |
128 | |
129 debugRegisterShape(this); | |
130 } | |
131 | |
132 protected ShapeImpl(Layout layout, ShapeImpl parent, ObjectType operations, Object sharedData, PropertyMap propertyMap, Allocator allocator, int id) { | |
133 this(layout, parent, operations, sharedData, propertyMap, ((BaseAllocator) allocator).objectArraySize, ((BaseAllocator) allocator).objectFieldSize, | |
134 ((BaseAllocator) allocator).primitiveFieldSize, ((BaseAllocator) allocator).primitiveArraySize, ((BaseAllocator) allocator).hasPrimitiveArray, id); | |
135 } | |
136 | |
137 @SuppressWarnings("hiding") | |
138 protected abstract ShapeImpl createShape(Layout layout, Object sharedData, ShapeImpl parent, ObjectType operations, PropertyMap propertyMap, Allocator allocator, int id); | |
139 | |
140 protected ShapeImpl(Layout layout, ObjectType operations, Object sharedData, int id) { | |
141 this(layout, null, operations, sharedData, PropertyMap.empty(), layout.createAllocator(), id); | |
142 } | |
143 | |
144 private static int makePropertyCount(ShapeImpl parent, PropertyMap propertyMap) { | |
145 return parent.propertyCount + ((propertyMap.size() > parent.propertyMap.size() && !propertyMap.getLastProperty().isHidden() && !propertyMap.getLastProperty().isShadow()) ? 1 : 0); | |
146 } | |
147 | |
148 private static Property[] makePropertiesList(ShapeImpl parent, PropertyMap propertyMap) { | |
149 Property[] properties = parent.propertyArray; | |
150 if (properties != null && propertyMap.size() != parent.propertyMap.size()) { | |
151 Property lastProperty = propertyMap.getLastProperty(); | |
152 if (lastProperty != null && !lastProperty.isHidden()) { | |
153 propertyListAllocCount.inc(); | |
154 if (!lastProperty.isShadow()) { | |
155 properties = Arrays.copyOf(properties, properties.length + 1); | |
156 properties[properties.length - 1] = lastProperty; | |
157 } else { | |
158 properties = Arrays.copyOf(properties, properties.length); | |
159 for (int i = 0; i < properties.length; i++) { | |
160 if (properties[i].isSame(lastProperty)) { | |
161 properties[i] = lastProperty; | |
162 } | |
163 } | |
164 } | |
165 } else { | |
166 propertyListShareCount.inc(); | |
167 } | |
168 } | |
169 return properties; | |
170 } | |
171 | |
172 @Override | |
173 public final Property getLastProperty() { | |
174 return propertyMap.getLastProperty(); | |
175 } | |
176 | |
177 @Override | |
178 public final int getId() { | |
179 return this.id; | |
180 } | |
181 | |
182 /** | |
183 * Calculate array size for the given number of elements. | |
184 */ | |
185 private static int capacityFromSize(int size) { | |
186 if (size == 0) { | |
187 return 0; | |
188 } else if (size < 4) { | |
189 return 4; | |
190 } else if (size < 32) { | |
191 return ((size + 7) / 8) * 8; | |
192 } else { | |
193 return ((size + 15) / 16) * 16; | |
194 } | |
195 } | |
196 | |
197 @Override | |
198 public final int getObjectArraySize() { | |
199 return objectArraySize; | |
200 } | |
201 | |
202 @Override | |
203 public final int getObjectFieldSize() { | |
204 return objectFieldSize; | |
205 } | |
206 | |
207 @Override | |
208 public final int getPrimitiveFieldSize() { | |
209 return primitiveFieldSize; | |
210 } | |
211 | |
212 @Override | |
213 public final int getObjectArrayCapacity() { | |
214 return objectArrayCapacity; | |
215 } | |
216 | |
217 @Override | |
218 public final int getPrimitiveArrayCapacity() { | |
219 return primitiveArrayCapacity; | |
220 } | |
221 | |
222 @Override | |
223 public final int getPrimitiveArraySize() { | |
224 return primitiveArraySize; | |
225 } | |
226 | |
227 @Override | |
228 public final boolean hasPrimitiveArray() { | |
229 return hasPrimitiveArray; | |
230 } | |
231 | |
232 /** | |
233 * Get the (parent) shape that holds the given property. | |
234 */ | |
235 public final ShapeImpl getShapeFromProperty(Object propertyName) { | |
236 ShapeImpl current = this; | |
237 while (current != getRoot()) { | |
238 if (current.getLastProperty().getKey().equals(propertyName)) { | |
239 return current; | |
240 } | |
241 current = current.getParent(); | |
242 } | |
243 | |
244 return null; | |
245 } | |
246 | |
247 /** | |
248 * Get the (parent) shape that holds the given property. | |
249 */ | |
250 public final ShapeImpl getShapeFromProperty(Property prop) { | |
251 ShapeImpl current = this; | |
252 while (current != getRoot()) { | |
253 if (current.getLastProperty().equals(prop)) { | |
254 return current; | |
255 } | |
256 current = current.parent; | |
257 } | |
258 | |
259 return null; | |
260 } | |
261 | |
262 /** | |
263 * Get a property entry by string name. | |
264 * | |
265 * @param key the name to look up | |
266 * @return a Property object, or null if not found | |
267 */ | |
268 @Override | |
269 @TruffleBoundary | |
270 public final Property getProperty(Object key) { | |
271 // return this.propertyMap.get(propertyName); | |
272 PropertyMap current = this.propertyMap; | |
273 while (current.getLastProperty() != null) { | |
274 if (current.getLastProperty().getKey().equals(key)) { | |
275 return current.getLastProperty(); | |
276 } | |
277 current = current.getParentMap(); | |
278 } | |
279 | |
280 return null; | |
281 } | |
282 | |
283 protected final void addTransition(Transition transition, ShapeImpl next) { | |
284 assert next.getParent() == this; | |
285 addTransitionInternal(transition, next); | |
286 } | |
287 | |
288 public final void addNonlinearTransition(Transition transition, ShapeImpl next) { | |
289 assert next.getParent() != this; | |
290 addTransitionInternal(transition, next); | |
291 } | |
292 | |
293 private void addTransitionInternal(Transition transition, ShapeImpl next) { | |
294 getTransitionMapForWrite().put(transition, next); | |
295 } | |
296 | |
297 public final Map<Transition, ShapeImpl> getTransitionMapForRead() { | |
298 return transitionMap != null ? transitionMap : Collections.<Transition, ShapeImpl> emptyMap(); | |
299 } | |
300 | |
301 private Map<Transition, ShapeImpl> getTransitionMapForWrite() { | |
302 if (transitionMap != null) { | |
303 return transitionMap; | |
304 } else { | |
305 invalidateLeafAssumption(); | |
306 return transitionMap = new HashMap<>(); | |
307 } | |
308 } | |
309 | |
310 public final PropertyMap getPropertyMap() { | |
311 return propertyMap; | |
312 } | |
313 | |
314 /** | |
315 * Add a new property in the map, yielding a new or cached Shape object. | |
316 * | |
317 * @param property the property to add | |
318 * @return the new Shape | |
319 */ | |
320 @TruffleBoundary | |
321 @Override | |
322 public ShapeImpl addProperty(Property property) { | |
323 assert isValid(); | |
324 ShapeImpl nextShape = addPropertyInternal(property); | |
325 objectType.onPropertyAdded(property, this, nextShape); | |
326 return nextShape; | |
327 } | |
328 | |
329 /** | |
330 * Add a new property in the map, yielding a new or cached Shape object. | |
331 * | |
332 * In contrast to {@link ShapeImpl#addProperty(Property)}, this method does not care about | |
333 * obsolete shapes. | |
334 * | |
335 * @see #addProperty(Property) | |
336 */ | |
337 private ShapeImpl addPropertyInternal(Property prop) { | |
338 CompilerAsserts.neverPartOfCompilation(); | |
339 assert prop.isShadow() || !(this.hasProperty(prop.getKey())) : "duplicate property"; | |
340 assert !getPropertyListInternal(false).contains(prop); | |
341 // invalidatePropertyAssumption(prop.getName()); | |
342 | |
343 Transition.AddTransition key = new Transition.AddTransition(prop); | |
344 Map<Transition, ShapeImpl> transitionMapForRead = this.getTransitionMapForRead(); | |
345 ShapeImpl cachedShape = transitionMapForRead.get(key); | |
346 if (cachedShape != null) { // Shape already exists? | |
347 shapeCacheHitCount.inc(); | |
348 return (ShapeImpl) layout.getStrategy().returnCached(cachedShape); | |
349 } | |
350 shapeCacheMissCount.inc(); | |
351 | |
352 ShapeImpl oldShape = (ShapeImpl) layout.getStrategy().ensureSpace(this, prop.getLocation()); | |
353 | |
354 ShapeImpl newShape = makeShapeWithAddedProperty(oldShape, key); | |
355 oldShape.addTransition(key, newShape); | |
356 return newShape; | |
357 } | |
358 | |
359 protected ShapeImpl cloneRoot(ShapeImpl from, Object newSharedData) { | |
360 return createShape(from.layout, newSharedData, null, from.objectType, from.propertyMap, from.allocator(), from.id); | |
361 } | |
362 | |
363 /** | |
364 * Create a separate clone of a shape. | |
365 * | |
366 * @param newParent the cloned parent shape | |
367 */ | |
368 protected final ShapeImpl cloneOnto(ShapeImpl newParent) { | |
369 ShapeImpl from = this; | |
370 ShapeImpl newShape = createShape(newParent.layout, newParent.sharedData, newParent, from.objectType, from.propertyMap, from.allocator(), newParent.id); | |
371 | |
372 shapeCloneCount.inc(); | |
373 | |
374 // (aw) need to have this transition for obsolescence | |
375 newParent.addTransition(getTransitionFromParent(), newShape); | |
376 return newShape; | |
377 } | |
378 | |
379 private Transition getTransitionFromParent() { | |
380 for (Map.Entry<Transition, ShapeImpl> property : parent.getTransitionMapForRead().entrySet()) { | |
381 if (property.getValue() == this) { | |
382 return property.getKey(); | |
383 } | |
384 } | |
385 throw new NoSuchElementException(); | |
386 } | |
387 | |
388 /** | |
389 * Create a new shape that adds a property to the parent shape. | |
390 */ | |
391 private static ShapeImpl makeShapeWithAddedProperty(ShapeImpl parent, AddTransition addTransition) { | |
392 Property addend = addTransition.getProperty(); | |
393 BaseAllocator allocator = parent.allocator().addLocation(addend.getLocation()); | |
394 | |
395 PropertyMap newPropertyMap = parent.propertyMap.putCopy(addend); | |
396 | |
397 ShapeImpl newShape = parent.createShape(parent.layout, parent.sharedData, parent, parent.objectType, newPropertyMap, allocator, parent.id); | |
398 assert ((LocationImpl) addend.getLocation()).primitiveArrayCount() == 0 || newShape.hasPrimitiveArray; | |
399 assert newShape.depth == allocator.depth; | |
400 return newShape; | |
401 } | |
402 | |
403 /** | |
404 * Create a new shape that reserves the primitive extension array field. | |
405 */ | |
406 private static ShapeImpl makeShapeWithPrimitiveExtensionArray(ShapeImpl parent) { | |
407 assert parent.getLayout().hasPrimitiveExtensionArray(); | |
408 assert !parent.hasPrimitiveArray(); | |
409 BaseAllocator allocator = parent.allocator().addLocation(parent.getLayout().getPrimitiveArrayLocation()); | |
410 ShapeImpl newShape = parent.createShape(parent.layout, parent.sharedData, parent, parent.objectType, parent.propertyMap, allocator, parent.id); | |
411 assert newShape.hasPrimitiveArray(); | |
412 assert newShape.depth == allocator.depth; | |
413 return newShape; | |
414 } | |
415 | |
416 private ShapeImpl addPrimitiveExtensionArray() { | |
417 assert layout.hasPrimitiveExtensionArray() && !hasPrimitiveArray(); | |
418 Transition key = new Transition.ReservePrimitiveArrayTransition(); | |
419 ShapeImpl cachedShape = this.getTransitionMapForRead().get(key); | |
420 if (cachedShape != null) { | |
421 shapeCacheHitCount.inc(); | |
422 return (ShapeImpl) layout.getStrategy().returnCached(cachedShape); | |
423 } | |
424 shapeCacheMissCount.inc(); | |
425 | |
426 ShapeImpl oldShape = (ShapeImpl) layout.getStrategy().ensureSpace(this, layout.getPrimitiveArrayLocation()); | |
427 ShapeImpl newShape = makeShapeWithPrimitiveExtensionArray(oldShape); | |
428 oldShape.addTransition(key, newShape); | |
429 return newShape; | |
430 } | |
431 | |
432 /** | |
433 * Are these two shapes related, i.e. do they have the same root? | |
434 * | |
435 * @param other Shape to compare to | |
436 * @return true if one shape is an upcast of the other, or the Shapes are equal | |
437 */ | |
438 @Override | |
439 public boolean isRelated(Shape other) { | |
440 if (this == other) { | |
441 return true; | |
442 } | |
443 if (this.getRoot() == getRoot()) { | |
444 return true; | |
445 } | |
446 return false; | |
447 } | |
448 | |
449 /** | |
450 * Get a list of all properties that this Shape stores. | |
451 * | |
452 * @return list of properties | |
453 */ | |
454 @TruffleBoundary | |
455 @Override | |
456 public final List<Property> getPropertyList(Pred<Property> filter) { | |
457 LinkedList<Property> props = new LinkedList<>(); | |
458 next: for (ShapeImpl current = this; current != getRoot(); current = current.parent) { | |
459 Property currentProperty = current.getLastProperty(); | |
460 if (!currentProperty.isHidden() && filter.test(currentProperty)) { | |
461 if (currentProperty.getLocation() instanceof DeclaredLocation) { | |
462 for (Iterator<Property> iter = props.iterator(); iter.hasNext();) { | |
463 Property other = iter.next(); | |
464 if (other.isShadow() && other.getKey().equals(currentProperty.getKey())) { | |
465 iter.remove(); | |
466 props.addFirst(other); | |
467 continue next; | |
468 } | |
469 } | |
470 } | |
471 props.addFirst(currentProperty); | |
472 } | |
473 } | |
474 return props; | |
475 } | |
476 | |
477 @Override | |
478 public final List<Property> getPropertyList() { | |
479 return getPropertyList(ALL); | |
480 } | |
481 | |
482 /** | |
483 * Returns all (also hidden) Property objects in this shape. | |
484 * | |
485 * @param ascending desired order | |
486 */ | |
487 @TruffleBoundary | |
488 @Override | |
489 public final List<Property> getPropertyListInternal(boolean ascending) { | |
490 LinkedList<Property> props = new LinkedList<>(); | |
491 for (ShapeImpl current = this; current != getRoot(); current = current.parent) { | |
492 if (ascending) { | |
493 props.addFirst(current.getLastProperty()); | |
494 } else { | |
495 props.add(current.getLastProperty()); | |
496 } | |
497 } | |
498 return props; | |
499 } | |
500 | |
501 /** | |
502 * Get a list of all (visible) property names in insertion order. | |
503 * | |
504 * @return list of property names | |
505 */ | |
506 @TruffleBoundary | |
507 @Override | |
508 public final List<Object> getKeyList(Pred<Property> filter) { | |
509 LinkedList<Object> keys = new LinkedList<>(); | |
510 for (ShapeImpl current = this; current != getRoot(); current = current.parent) { | |
511 Property currentProperty = current.getLastProperty(); | |
512 if (!currentProperty.isHidden() && filter.test(currentProperty) && !currentProperty.isShadow()) { | |
513 keys.addFirst(currentProperty.getKey()); | |
514 } | |
515 } | |
516 return keys; | |
517 } | |
518 | |
519 @Override | |
520 public final List<Object> getKeyList() { | |
521 return getKeyList(ALL); | |
522 } | |
523 | |
524 @Override | |
525 public Iterable<Object> getKeys() { | |
526 return getKeyList(); | |
527 } | |
528 | |
529 public final void setTypeTransition(ShapeImpl successorShape, Property before, Property after) { | |
530 getTransitionMapForWrite().put(new Transition.TypeTransition(before, after), successorShape); | |
531 } | |
532 | |
533 private static Assumption createValidAssumption() { | |
534 return Truffle.getRuntime().createAssumption("valid shape"); | |
535 } | |
536 | |
537 @Override | |
538 public final Assumption getValidAssumption() { | |
539 return validAssumption; | |
540 } | |
541 | |
542 @Override | |
543 public final boolean isValid() { | |
544 return getValidAssumption().isValid(); | |
545 } | |
546 | |
547 private static Assumption createLeafAssumption() { | |
548 return Truffle.getRuntime().createAssumption("leaf shape"); | |
549 } | |
550 | |
551 @Override | |
552 public final Assumption getLeafAssumption() { | |
553 return leafAssumption; | |
554 } | |
555 | |
556 @Override | |
557 public final boolean isLeaf() { | |
558 return getLeafAssumption().isValid(); | |
559 } | |
560 | |
561 private void invalidateLeafAssumption() { | |
562 getLeafAssumption().invalidate(); | |
563 } | |
564 | |
565 @Override | |
566 public String toString() { | |
567 return toStringLimit(Integer.MAX_VALUE); | |
568 } | |
569 | |
570 @TruffleBoundary | |
571 public String toStringLimit(int limit) { | |
572 StringBuilder sb = new StringBuilder(); | |
573 sb.append('@'); | |
574 sb.append(Integer.toHexString(hashCode())); | |
575 if (!isValid()) { | |
576 sb.append('!'); | |
577 } | |
578 | |
579 sb.append("{"); | |
580 for (Iterator<Property> iterator = propertyMap.reverseOrderValues().iterator(); iterator.hasNext();) { | |
581 Property p = iterator.next(); | |
582 sb.append(p); | |
583 if (iterator.hasNext()) { | |
584 sb.append(", "); | |
585 } | |
586 if (sb.length() >= limit) { | |
587 sb.append("..."); | |
588 break; | |
589 } | |
590 sb.append("\n"); | |
591 } | |
592 sb.append("}"); | |
593 | |
594 return sb.toString(); | |
595 } | |
596 | |
597 @Override | |
598 public final ShapeImpl getParent() { | |
599 return parent; | |
600 } | |
601 | |
602 public final int getDepth() { | |
603 return depth; | |
604 } | |
605 | |
606 @Override | |
607 public final boolean hasProperty(Object name) { | |
608 return getProperty(name) != null; | |
609 } | |
610 | |
611 @TruffleBoundary | |
612 @Override | |
613 public final ShapeImpl removeProperty(Property prop) { | |
614 RemoveTransition transition = new RemoveTransition(prop); | |
615 ShapeImpl cachedShape = getTransitionMapForRead().get(transition); | |
616 if (cachedShape != null) { | |
617 return (ShapeImpl) layout.getStrategy().returnCached(cachedShape); | |
618 } | |
619 | |
620 ShapeImpl shape = getShapeFromProperty(prop); | |
621 if (shape != null) { | |
622 List<Property> properties = new ArrayList<>(); | |
623 ShapeImpl current = this; | |
624 while (current != shape) { | |
625 properties.add(current.getLastProperty()); | |
626 current = current.parent; | |
627 } | |
628 ShapeImpl newShape = shape.parent; | |
629 for (ListIterator<Property> iterator = properties.listIterator(properties.size()); iterator.hasPrevious();) { | |
630 Property previous = iterator.previous(); | |
631 newShape = newShape.append(previous); | |
632 } | |
633 | |
634 getTransitionMapForWrite().put(transition, newShape); | |
635 return newShape; | |
636 } else { | |
637 return null; | |
638 } | |
639 } | |
640 | |
641 @TruffleBoundary | |
642 @Override | |
643 public final ShapeImpl append(Property oldProperty) { | |
644 return addProperty(oldProperty.relocate(allocator().moveLocation(oldProperty.getLocation()))); | |
645 } | |
646 | |
647 @Override | |
648 public final BaseAllocator allocator() { | |
649 return layout.getStrategy().createAllocator(this); | |
650 } | |
651 | |
652 /** | |
653 * Duplicate shape exchanging existing property with new property. | |
654 */ | |
655 @Override | |
656 public final ShapeImpl replaceProperty(Property oldProperty, Property newProp) { | |
657 ShapeImpl top = this; | |
658 List<Property> propertyList = new ArrayList<>(); | |
659 boolean found = false; | |
660 while (top != getRoot() && !found) { | |
661 Property prop = top.getLastProperty(); | |
662 propertyList.add(prop); | |
663 if (prop.getKey().equals(newProp.getKey())) { | |
664 found = true; | |
665 } | |
666 top = top.parent; | |
667 } | |
668 ShapeImpl newShape = top; | |
669 for (ListIterator<Property> iterator = propertyList.listIterator(propertyList.size()); iterator.hasPrevious();) { | |
670 Property prop = iterator.previous(); | |
671 if (prop.getKey().equals(newProp.getKey())) { | |
672 newShape = newShape.addProperty(newProp); | |
673 } else { | |
674 newShape = newShape.addProperty(prop); | |
675 } | |
676 } | |
677 return newShape; | |
678 } | |
679 | |
680 /** | |
681 * Find lowest common ancestor of two related shapes. | |
682 */ | |
683 public static ShapeImpl findCommonAncestor(ShapeImpl left, ShapeImpl right) { | |
684 if (!left.isRelated(right)) { | |
685 throw new IllegalArgumentException("shapes must have the same root"); | |
686 } else if (left == right) { | |
687 return left; | |
688 } | |
689 int leftLength = left.depth; | |
690 int rightLength = right.depth; | |
691 ShapeImpl leftPtr = left; | |
692 ShapeImpl rightPtr = right; | |
693 while (leftLength > rightLength) { | |
694 leftPtr = leftPtr.parent; | |
695 leftLength--; | |
696 } | |
697 while (rightLength > leftLength) { | |
698 rightPtr = rightPtr.parent; | |
699 rightLength--; | |
700 } | |
701 while (leftPtr != rightPtr) { | |
702 leftPtr = leftPtr.parent; | |
703 rightPtr = rightPtr.parent; | |
704 } | |
705 return leftPtr; | |
706 } | |
707 | |
708 /** | |
709 * For copying over properties after exchanging the prototype of an object. | |
710 */ | |
711 @TruffleBoundary | |
712 @Override | |
713 public final ShapeImpl copyOverPropertiesInternal(Shape destination) { | |
714 assert ((ShapeImpl) destination).getDepth() == 0; | |
715 List<Property> properties = this.getPropertyListInternal(true); | |
716 ShapeImpl newShape = ((ShapeImpl) destination).addPropertiesInternal(properties); | |
717 return newShape; | |
718 } | |
719 | |
720 private ShapeImpl addPropertiesInternal(List<Property> properties) { | |
721 ShapeImpl newShape = this; | |
722 for (Property p : properties) { | |
723 newShape = newShape.addPropertyInternal(p); | |
724 } | |
725 return newShape; | |
726 } | |
727 | |
728 /** | |
729 * NB: this is not an accurate property count. | |
730 */ | |
731 @Override | |
732 public final int getPropertyCount() { | |
733 return propertyCount; | |
734 } | |
735 | |
736 /** | |
737 * Find difference between two shapes. | |
738 * | |
739 * @see ObjectStorageOptions#TraceReshape | |
740 */ | |
741 public static List<Property> diff(Shape oldShape, Shape newShape) { | |
742 List<Property> oldList = oldShape.getPropertyListInternal(false); | |
743 List<Property> newList = newShape.getPropertyListInternal(false); | |
744 | |
745 List<Property> diff = new ArrayList<>(oldList); | |
746 diff.addAll(newList); | |
747 List<Property> intersection = new ArrayList<>(oldList); | |
748 intersection.retainAll(newList); | |
749 diff.removeAll(intersection); | |
750 return diff; | |
751 } | |
752 | |
753 @Override | |
754 public ObjectType getObjectType() { | |
755 return objectType; | |
756 } | |
757 | |
758 @Override | |
759 public ShapeImpl getRoot() { | |
760 return root; | |
761 } | |
762 | |
763 @Override | |
764 public final boolean check(DynamicObject subject) { | |
765 return subject.getShape() == this; | |
766 } | |
767 | |
768 @Override | |
769 public final LayoutImpl getLayout() { | |
770 return layout; | |
771 } | |
772 | |
773 @Override | |
774 public final Object getData() { | |
775 return extraData; | |
776 } | |
777 | |
778 @Override | |
779 public final Object getSharedData() { | |
780 return sharedData; | |
781 } | |
782 | |
783 @TruffleBoundary | |
784 @Override | |
785 public final boolean hasTransitionWithKey(Object key) { | |
786 for (Transition transition : getTransitionMapForRead().keySet()) { | |
787 if (transition instanceof PropertyTransition) { | |
788 if (((PropertyTransition) transition).getProperty().getKey().equals(key)) { | |
789 return true; | |
790 } | |
791 } | |
792 } | |
793 return false; | |
794 } | |
795 | |
796 /** | |
797 * Clone off a separate shape with new shared data. | |
798 */ | |
799 @TruffleBoundary | |
800 @Override | |
801 public final ShapeImpl createSeparateShape(Object newSharedData) { | |
802 if (parent == null) { | |
803 return cloneRoot(this, newSharedData); | |
804 } else { | |
805 return this.cloneOnto(parent.createSeparateShape(newSharedData)); | |
806 } | |
807 } | |
808 | |
809 @Override | |
810 @TruffleBoundary | |
811 public final ShapeImpl changeType(ObjectType newOps) { | |
812 OperationsTransition transition = new OperationsTransition(newOps); | |
813 ShapeImpl cachedShape = getTransitionMapForRead().get(transition); | |
814 if (cachedShape != null) { | |
815 return cachedShape; | |
816 } else { | |
817 ShapeImpl newShape = createShape(layout, extraData, this, newOps, propertyMap, allocator(), id); | |
818 addTransition(transition, newShape); | |
819 return newShape; | |
820 } | |
821 } | |
822 | |
823 @Override | |
824 public final Shape reservePrimitiveExtensionArray() { | |
825 if (layout.hasPrimitiveExtensionArray() && !hasPrimitiveArray()) { | |
826 return addPrimitiveExtensionArray(); | |
827 } | |
828 return this; | |
829 } | |
830 | |
831 @Override | |
832 public final Iterable<Property> getProperties() { | |
833 if (getPropertyCount() != 0 && propertyArray == null) { | |
834 CompilerDirectives.transferToInterpreter(); | |
835 propertyArray = createPropertiesArray(); | |
836 } | |
837 return new Iterable<Property>() { | |
838 public Iterator<Property> iterator() { | |
839 return new Iterator<Property>() { | |
840 private int cursor; | |
841 | |
842 public boolean hasNext() { | |
843 return cursor < getPropertyCount(); | |
844 } | |
845 | |
846 public Property next() { | |
847 if (hasNext()) { | |
848 return propertyArray[cursor++]; | |
849 } | |
850 throw new NoSuchElementException(); | |
851 } | |
852 | |
853 public void remove() { | |
854 throw new UnsupportedOperationException(); | |
855 } | |
856 }; | |
857 } | |
858 }; | |
859 } | |
860 | |
861 private Property[] createPropertiesArray() { | |
862 propertyListAllocCount.inc(); | |
863 Property[] propertiesArray = new Property[getPropertyCount()]; | |
864 List<Property> ownProperties = getPropertyList(ALL); | |
865 assert ownProperties.size() == getPropertyCount(); | |
866 for (int i = 0; i < getPropertyCount(); i++) { | |
867 propertiesArray[i] = ownProperties.get(i); | |
868 } | |
869 return propertiesArray; | |
870 } | |
871 | |
872 @Override | |
873 public final DynamicObject newInstance() { | |
874 return layout.newInstance(this); | |
875 } | |
876 | |
877 @Override | |
878 public final DynamicObjectFactory createFactory() { | |
879 final List<Property> properties = getPropertyListInternal(true); | |
880 for (Iterator<Property> iterator = properties.iterator(); iterator.hasNext();) { | |
881 Property property = iterator.next(); | |
882 // skip non-instance fields | |
883 assert property.getLocation() != layout.getPrimitiveArrayLocation(); | |
884 if (property.getLocation() instanceof ValueLocation) { | |
885 iterator.remove(); | |
886 } | |
887 } | |
888 | |
889 return new DynamicObjectFactory() { | |
890 @CompilationFinal private final PropertyImpl[] instanceFields = properties.toArray(new PropertyImpl[properties.size()]); | |
891 | |
892 @ExplodeLoop | |
893 public DynamicObject newInstance(Object... initialValues) { | |
894 DynamicObject store = ShapeImpl.this.newInstance(); | |
895 for (int i = 0; i < instanceFields.length; i++) { | |
896 instanceFields[i].setInternal(store, initialValues[i]); | |
897 } | |
898 return store; | |
899 } | |
900 | |
901 public Shape getShape() { | |
902 return ShapeImpl.this; | |
903 } | |
904 }; | |
905 } | |
906 | |
907 @Override | |
908 public Object getMutex() { | |
909 return getRoot(); | |
910 } | |
911 | |
912 @Override | |
913 public Shape tryMerge(Shape other) { | |
914 return null; | |
915 } | |
916 | |
917 public abstract static class BaseAllocator extends Allocator { | |
918 protected final LayoutImpl layout; | |
919 protected int objectArraySize; | |
920 protected int objectFieldSize; | |
921 protected int primitiveFieldSize; | |
922 protected int primitiveArraySize; | |
923 protected boolean hasPrimitiveArray; | |
924 protected int depth; | |
925 | |
926 protected BaseAllocator(LayoutImpl layout) { | |
927 this.layout = layout; | |
928 } | |
929 | |
930 protected BaseAllocator(ShapeImpl shape) { | |
931 this(shape.getLayout()); | |
932 this.objectArraySize = shape.objectArraySize; | |
933 this.objectFieldSize = shape.objectFieldSize; | |
934 this.primitiveFieldSize = shape.primitiveFieldSize; | |
935 this.primitiveArraySize = shape.primitiveArraySize; | |
936 this.hasPrimitiveArray = shape.hasPrimitiveArray; | |
937 this.depth = shape.depth; | |
938 } | |
939 | |
940 protected abstract Location moveLocation(Location oldLocation); | |
941 | |
942 protected abstract Location newObjectLocation(boolean useFinal, boolean nonNull); | |
943 | |
944 protected abstract Location newTypedObjectLocation(boolean useFinal, Class<?> type, boolean nonNull); | |
945 | |
946 protected abstract Location newIntLocation(boolean useFinal); | |
947 | |
948 protected abstract Location newDoubleLocation(boolean useFinal); | |
949 | |
950 protected abstract Location newLongLocation(boolean useFinal); | |
951 | |
952 protected abstract Location newBooleanLocation(boolean useFinal); | |
953 | |
954 @Override | |
955 public final Location constantLocation(Object value) { | |
956 return new ConstantLocation(value); | |
957 } | |
958 | |
959 @Override | |
960 protected Location locationForValue(Object value, boolean useFinal, boolean nonNull) { | |
961 if (value instanceof Integer) { | |
962 return newIntLocation(useFinal); | |
963 } else if (value instanceof Double) { | |
964 return newDoubleLocation(useFinal); | |
965 } else if (value instanceof Long) { | |
966 return newLongLocation(useFinal); | |
967 } else if (value instanceof Boolean) { | |
968 return newBooleanLocation(useFinal); | |
969 } else if (ObjectStorageOptions.TypedObjectLocations && value != null) { | |
970 return newTypedObjectLocation(useFinal, value.getClass(), nonNull); | |
971 } | |
972 return newObjectLocation(useFinal, nonNull && value != null); | |
973 } | |
974 | |
975 protected abstract Location locationForValueUpcast(Object value, Location oldLocation); | |
976 | |
977 @Override | |
978 protected Location locationForType(Class<?> type, boolean useFinal, boolean nonNull) { | |
979 if (type == int.class) { | |
980 return newIntLocation(useFinal); | |
981 } else if (type == double.class) { | |
982 return newDoubleLocation(useFinal); | |
983 } else if (type == long.class) { | |
984 return newLongLocation(useFinal); | |
985 } else if (type == boolean.class) { | |
986 return newBooleanLocation(useFinal); | |
987 } else if (ObjectStorageOptions.TypedObjectLocations && type != null && type != Object.class) { | |
988 assert !type.isPrimitive() : "unsupported primitive type"; | |
989 return newTypedObjectLocation(useFinal, type, nonNull); | |
990 } | |
991 return newObjectLocation(useFinal, nonNull); | |
992 } | |
993 | |
994 protected Location newDualLocation(Class<?> type) { | |
995 return new DualLocation((InternalLongLocation) newLongLocation(false), (ObjectLocation) newObjectLocation(false, false), layout, type); | |
996 } | |
997 | |
998 protected DualLocation newDualLocationForValue(Object value) { | |
999 Class<?> initialType = null; | |
1000 if (value instanceof Integer) { | |
1001 initialType = int.class; | |
1002 } else if (value instanceof Double) { | |
1003 initialType = double.class; | |
1004 } else if (value instanceof Boolean) { | |
1005 initialType = boolean.class; | |
1006 } else { | |
1007 initialType = Object.class; | |
1008 } | |
1009 return new DualLocation((InternalLongLocation) newLongLocation(false), (ObjectLocation) newObjectLocation(false, false), layout, initialType); | |
1010 } | |
1011 | |
1012 protected Location newDeclaredDualLocation(Object value) { | |
1013 return new DeclaredDualLocation((InternalLongLocation) newLongLocation(false), (ObjectLocation) newObjectLocation(false, false), value, layout); | |
1014 } | |
1015 | |
1016 protected <T extends Location> T advance(T location0) { | |
1017 if (location0 instanceof LocationImpl) { | |
1018 LocationImpl location = (LocationImpl) location0; | |
1019 objectArraySize += location.objectArrayCount(); | |
1020 primitiveArraySize += location.primitiveArrayCount(); | |
1021 primitiveFieldSize += location.primitiveFieldCount(); | |
1022 if (layout.hasPrimitiveExtensionArray()) { | |
1023 hasPrimitiveArray |= location == layout.getPrimitiveArrayLocation() || location.primitiveArrayCount() != 0; | |
1024 objectFieldSize = location == layout.getPrimitiveArrayLocation() ? objectFieldSize : Math.max(objectFieldSize, layout.objectFieldIndex(location) + location.objectFieldCount()); | |
1025 } else { | |
1026 assert !hasPrimitiveArray && location.primitiveArrayCount() == 0; | |
1027 objectFieldSize += location.objectFieldCount(); | |
1028 } | |
1029 } | |
1030 depth++; | |
1031 return location0; | |
1032 } | |
1033 | |
1034 @Override | |
1035 public BaseAllocator addLocation(Location location) { | |
1036 advance(location); | |
1037 return this; | |
1038 } | |
1039 } | |
1040 | |
1041 private static void debugRegisterShape(ShapeImpl newShape) { | |
1042 if (ObjectStorageOptions.DumpShapes) { | |
1043 Debug.registerShape(newShape); | |
1044 } | |
1045 } | |
1046 | |
1047 /** | |
1048 * Match all filter. | |
1049 */ | |
1050 public static final Pred<Property> ALL = new Pred<Property>() { | |
1051 public boolean test(Property t) { | |
1052 return true; | |
1053 } | |
1054 }; | |
1055 | |
1056 private static final DebugCounter shapeCount = DebugCounter.create("Shapes allocated total"); | |
1057 private static final DebugCounter shapeCloneCount = DebugCounter.create("Shapes allocated cloned"); | |
1058 private static final DebugCounter shapeCacheHitCount = DebugCounter.create("Shape cache hits"); | |
1059 private static final DebugCounter shapeCacheMissCount = DebugCounter.create("Shape cache misses"); | |
1060 | |
1061 protected static final DebugCounter propertyListAllocCount = DebugCounter.create("Property lists allocated"); | |
1062 protected static final DebugCounter propertyListShareCount = DebugCounter.create("Property lists shared"); | |
1063 } |