# HG changeset patch
# User Andreas Woess <andreas.woess@jku.at>
# Date 1417712902 -3600
# Node ID 8bf798e8cf113d5760766a2f1c77c1bf4ebdf83c
# Parent  a306a94111a64a461c80800260d173a40785a4f5
OM: remember transition from parent and walk transitions instead of properties in replaceProperty,removeProperty

diff -r a306a94111a6 -r 8bf798e8cf11 graal/com.oracle.truffle.object.basic/src/com/oracle/truffle/object/basic/ShapeBasic.java
--- a/graal/com.oracle.truffle.object.basic/src/com/oracle/truffle/object/basic/ShapeBasic.java	Fri Nov 28 15:43:49 2014 +0100
+++ b/graal/com.oracle.truffle.object.basic/src/com/oracle/truffle/object/basic/ShapeBasic.java	Thu Dec 04 18:08:22 2014 +0100
@@ -30,13 +30,13 @@
         super(layout, operations, sharedData, id);
     }
 
-    public ShapeBasic(Layout layout, Object sharedData, ShapeImpl parent, ObjectType operations, PropertyMap propertyMap, Allocator allocator, int id) {
-        super(layout, parent, operations, sharedData, propertyMap, allocator, id);
+    public ShapeBasic(Layout layout, Object sharedData, ShapeImpl parent, ObjectType objectType, PropertyMap propertyMap, Transition transition, Allocator allocator, int id) {
+        super(layout, parent, objectType, sharedData, propertyMap, transition, allocator, id);
     }
 
     @SuppressWarnings("hiding")
     @Override
-    protected ShapeImpl createShape(Layout layout, Object sharedData, ShapeImpl parent, ObjectType operations, PropertyMap propertyMap, Allocator allocator, int id) {
-        return new ShapeBasic(layout, sharedData, parent, operations, propertyMap, allocator, id);
+    protected ShapeImpl createShape(Layout layout, Object sharedData, ShapeImpl parent, ObjectType objectType, PropertyMap propertyMap, Transition transition, Allocator allocator, int id) {
+        return new ShapeBasic(layout, sharedData, parent, objectType, propertyMap, transition, allocator, id);
     }
 }
diff -r a306a94111a6 -r 8bf798e8cf11 graal/com.oracle.truffle.object/src/com/oracle/truffle/object/ShapeImpl.java
--- a/graal/com.oracle.truffle.object/src/com/oracle/truffle/object/ShapeImpl.java	Fri Nov 28 15:43:49 2014 +0100
+++ b/graal/com.oracle.truffle.object/src/com/oracle/truffle/object/ShapeImpl.java	Thu Dec 04 18:08:22 2014 +0100
@@ -39,6 +39,7 @@
 import com.oracle.truffle.object.Transition.ObjectTypeTransition;
 import com.oracle.truffle.object.Transition.PropertyTransition;
 import com.oracle.truffle.object.Transition.RemovePropertyTransition;
+import com.oracle.truffle.object.Transition.ReservePrimitiveArrayTransition;
 
 /**
  * Shape objects create a mapping of Property objects to indexes. The mapping of those indexes to an
@@ -87,18 +88,24 @@
      */
     private HashMap<Transition, ShapeImpl> transitionMap;
 
+    private final Transition transitionFromParent;
+
     /**
      * Private constructor.
      *
-     * @see #ShapeImpl(Layout, ShapeImpl, ObjectType, Object, PropertyMap, BaseAllocator, int)
+     * @param parent predecessor shape
+     * @param transitionFromParent direct transition from parent shape
+     * @see #ShapeImpl(Layout, ShapeImpl, ObjectType, Object, PropertyMap, Transition,
+     *      BaseAllocator, int)
      */
-    private ShapeImpl(Layout layout, ShapeImpl parent, ObjectType operations, Object sharedData, PropertyMap propertyMap, int objectArraySize, int objectFieldSize, int primitiveFieldSize,
-                    int primitiveArraySize, boolean hasPrimitiveArray, int id) {
+    private ShapeImpl(Layout layout, ShapeImpl parent, ObjectType objectType, Object sharedData, PropertyMap propertyMap, Transition transitionFromParent, int objectArraySize, int objectFieldSize,
+                    int primitiveFieldSize, int primitiveArraySize, boolean hasPrimitiveArray, int id) {
         this.layout = (LayoutImpl) layout;
-        this.objectType = Objects.requireNonNull(operations);
+        this.objectType = Objects.requireNonNull(objectType);
         this.propertyMap = Objects.requireNonNull(propertyMap);
         this.root = parent != null ? parent.getRoot() : this;
         this.parent = parent;
+        this.transitionFromParent = transitionFromParent;
         this.objectArraySize = objectArraySize;
         this.objectArrayCapacity = capacityFromSize(objectArraySize);
         this.objectFieldSize = objectFieldSize;
@@ -124,21 +131,21 @@
         shapeCount.inc();
 
         this.sharedData = sharedData;
-        this.extraData = operations.createShapeData(this);
+        this.extraData = objectType.createShapeData(this);
 
         debugRegisterShape(this);
     }
 
-    protected ShapeImpl(Layout layout, ShapeImpl parent, ObjectType operations, Object sharedData, PropertyMap propertyMap, Allocator allocator, int id) {
-        this(layout, parent, operations, sharedData, propertyMap, ((BaseAllocator) allocator).objectArraySize, ((BaseAllocator) allocator).objectFieldSize,
+    protected ShapeImpl(Layout layout, ShapeImpl parent, ObjectType operations, Object sharedData, PropertyMap propertyMap, Transition transition, Allocator allocator, int id) {
+        this(layout, parent, operations, sharedData, propertyMap, transition, ((BaseAllocator) allocator).objectArraySize, ((BaseAllocator) allocator).objectFieldSize,
                         ((BaseAllocator) allocator).primitiveFieldSize, ((BaseAllocator) allocator).primitiveArraySize, ((BaseAllocator) allocator).hasPrimitiveArray, id);
     }
 
     @SuppressWarnings("hiding")
-    protected abstract ShapeImpl createShape(Layout layout, Object sharedData, ShapeImpl parent, ObjectType operations, PropertyMap propertyMap, Allocator allocator, int id);
+    protected abstract ShapeImpl createShape(Layout layout, Object sharedData, ShapeImpl parent, ObjectType operations, PropertyMap propertyMap, Transition transition, Allocator allocator, int id);
 
     protected ShapeImpl(Layout layout, ObjectType operations, Object sharedData, int id) {
-        this(layout, null, operations, sharedData, PropertyMap.empty(), layout.createAllocator(), id);
+        this(layout, null, operations, sharedData, PropertyMap.empty(), null, layout.createAllocator(), id);
     }
 
     private static int makePropertyCount(ShapeImpl parent, PropertyMap propertyMap) {
@@ -235,7 +242,7 @@
     public final ShapeImpl getShapeFromProperty(Object propertyName) {
         ShapeImpl current = this;
         while (current != getRoot()) {
-            if (current.getLastProperty().getKey().equals(propertyName)) {
+            if (current.getTransitionFromParent() instanceof AddPropertyTransition && ((AddPropertyTransition) current.getTransitionFromParent()).getProperty().getKey().equals(propertyName)) {
                 return current;
             }
             current = current.getParent();
@@ -250,7 +257,7 @@
     public final ShapeImpl getShapeFromProperty(Property prop) {
         ShapeImpl current = this;
         while (current != getRoot()) {
-            if (current.getLastProperty().equals(prop)) {
+            if (current.getTransitionFromParent() instanceof AddPropertyTransition && ((AddPropertyTransition) current.getTransitionFromParent()).getProperty().equals(prop)) {
                 return current;
             }
             current = current.parent;
@@ -280,12 +287,12 @@
         return null;
     }
 
-    protected final void addTransition(Transition transition, ShapeImpl next) {
+    protected final void addDirectTransition(Transition transition, ShapeImpl next) {
         assert next.getParent() == this;
         addTransitionInternal(transition, next);
     }
 
-    public final void addNonlinearTransition(Transition transition, ShapeImpl next) {
+    public final void addIndirectTransition(Transition transition, ShapeImpl next) {
         assert next.getParent() != this;
         addTransitionInternal(transition, next);
     }
@@ -340,7 +347,7 @@
         assert !getPropertyListInternal(false).contains(prop);
         // invalidatePropertyAssumption(prop.getName());
 
-        Transition.AddPropertyTransition key = new Transition.AddPropertyTransition(prop);
+        AddPropertyTransition key = new AddPropertyTransition(prop);
         Map<Transition, ShapeImpl> transitionMapForRead = this.getTransitionMapForRead();
         ShapeImpl cachedShape = transitionMapForRead.get(key);
         if (cachedShape != null) { // Shape already exists?
@@ -352,12 +359,12 @@
         ShapeImpl oldShape = (ShapeImpl) layout.getStrategy().ensureSpace(this, prop.getLocation());
 
         ShapeImpl newShape = makeShapeWithAddedProperty(oldShape, key);
-        oldShape.addTransition(key, newShape);
+        oldShape.addDirectTransition(key, newShape);
         return newShape;
     }
 
     protected ShapeImpl cloneRoot(ShapeImpl from, Object newSharedData) {
-        return createShape(from.layout, newSharedData, null, from.objectType, from.propertyMap, from.allocator(), from.id);
+        return createShape(from.layout, newSharedData, null, from.objectType, from.propertyMap, null, from.allocator(), from.id);
     }
 
     /**
@@ -367,22 +374,17 @@
      */
     protected final ShapeImpl cloneOnto(ShapeImpl newParent) {
         ShapeImpl from = this;
-        ShapeImpl newShape = createShape(newParent.layout, newParent.sharedData, newParent, from.objectType, from.propertyMap, from.allocator(), newParent.id);
+        ShapeImpl newShape = createShape(newParent.layout, newParent.sharedData, newParent, from.objectType, from.propertyMap, from.transitionFromParent, from.allocator(), newParent.id);
 
         shapeCloneCount.inc();
 
         // (aw) need to have this transition for obsolescence
-        newParent.addTransition(getTransitionFromParent(), newShape);
+        newParent.addDirectTransition(from.transitionFromParent, newShape);
         return newShape;
     }
 
-    private Transition getTransitionFromParent() {
-        for (Map.Entry<Transition, ShapeImpl> property : parent.getTransitionMapForRead().entrySet()) {
-            if (property.getValue() == this) {
-                return property.getKey();
-            }
-        }
-        throw new NoSuchElementException();
+    public final Transition getTransitionFromParent() {
+        return transitionFromParent;
     }
 
     /**
@@ -394,7 +396,7 @@
 
         PropertyMap newPropertyMap = parent.propertyMap.putCopy(addend);
 
-        ShapeImpl newShape = parent.createShape(parent.layout, parent.sharedData, parent, parent.objectType, newPropertyMap, allocator, parent.id);
+        ShapeImpl newShape = parent.createShape(parent.layout, parent.sharedData, parent, parent.objectType, newPropertyMap, addTransition, allocator, parent.id);
         assert ((LocationImpl) addend.getLocation()).primitiveArrayCount() == 0 || newShape.hasPrimitiveArray;
         assert newShape.depth == allocator.depth;
         return newShape;
@@ -403,11 +405,11 @@
     /**
      * Create a new shape that reserves the primitive extension array field.
      */
-    private static ShapeImpl makeShapeWithPrimitiveExtensionArray(ShapeImpl parent) {
+    private static ShapeImpl makeShapeWithPrimitiveExtensionArray(ShapeImpl parent, Transition transition) {
         assert parent.getLayout().hasPrimitiveExtensionArray();
         assert !parent.hasPrimitiveArray();
         BaseAllocator allocator = parent.allocator().addLocation(parent.getLayout().getPrimitiveArrayLocation());
-        ShapeImpl newShape = parent.createShape(parent.layout, parent.sharedData, parent, parent.objectType, parent.propertyMap, allocator, parent.id);
+        ShapeImpl newShape = parent.createShape(parent.layout, parent.sharedData, parent, parent.objectType, parent.propertyMap, transition, allocator, parent.id);
         assert newShape.hasPrimitiveArray();
         assert newShape.depth == allocator.depth;
         return newShape;
@@ -415,7 +417,7 @@
 
     private ShapeImpl addPrimitiveExtensionArray() {
         assert layout.hasPrimitiveExtensionArray() && !hasPrimitiveArray();
-        Transition key = new Transition.ReservePrimitiveArrayTransition();
+        Transition key = new ReservePrimitiveArrayTransition();
         ShapeImpl cachedShape = this.getTransitionMapForRead().get(key);
         if (cachedShape != null) {
             shapeCacheHitCount.inc();
@@ -424,8 +426,8 @@
         shapeCacheMissCount.inc();
 
         ShapeImpl oldShape = (ShapeImpl) layout.getStrategy().ensureSpace(this, layout.getPrimitiveArrayLocation());
-        ShapeImpl newShape = makeShapeWithPrimitiveExtensionArray(oldShape);
-        oldShape.addTransition(key, newShape);
+        ShapeImpl newShape = makeShapeWithPrimitiveExtensionArray(oldShape, key);
+        oldShape.addDirectTransition(key, newShape);
         return newShape;
     }
 
@@ -617,16 +619,16 @@
 
         ShapeImpl shape = getShapeFromProperty(prop);
         if (shape != null) {
-            List<Property> properties = new ArrayList<>();
+            List<Transition> transitionList = new ArrayList<>();
             ShapeImpl current = this;
             while (current != shape) {
-                properties.add(current.getLastProperty());
+                transitionList.add(current.getTransitionFromParent());
                 current = current.parent;
             }
             ShapeImpl newShape = shape.parent;
-            for (ListIterator<Property> iterator = properties.listIterator(properties.size()); iterator.hasPrevious();) {
-                Property previous = iterator.previous();
-                newShape = newShape.append(previous);
+            for (ListIterator<Transition> iterator = transitionList.listIterator(transitionList.size()); iterator.hasPrevious();) {
+                Transition previous = iterator.previous();
+                newShape = newShape.applyTransition(previous, true);
             }
 
             getTransitionMapForWrite().put(transition, newShape);
@@ -642,6 +644,18 @@
         return addProperty(oldProperty.relocate(allocator().moveLocation(oldProperty.getLocation())));
     }
 
+    public final ShapeImpl applyTransition(Transition transition, boolean append) {
+        if (transition instanceof AddPropertyTransition) {
+            return append ? append(((AddPropertyTransition) transition).getProperty()) : addProperty(((AddPropertyTransition) transition).getProperty());
+        } else if (transition instanceof ObjectTypeTransition) {
+            return changeType(((ObjectTypeTransition) transition).getObjectType());
+        } else if (transition instanceof ReservePrimitiveArrayTransition) {
+            return reservePrimitiveExtensionArray();
+        } else {
+            throw new UnsupportedOperationException();
+        }
+    }
+
     @Override
     public final BaseAllocator allocator() {
         return layout.getStrategy().createAllocator(this);
@@ -653,23 +667,23 @@
     @Override
     public final ShapeImpl replaceProperty(Property oldProperty, Property newProp) {
         ShapeImpl top = this;
-        List<Property> propertyList = new ArrayList<>();
+        List<Transition> transitionList = new ArrayList<>();
         boolean found = false;
         while (top != getRoot() && !found) {
-            Property prop = top.getLastProperty();
-            propertyList.add(prop);
-            if (prop.getKey().equals(newProp.getKey())) {
+            Transition transition = top.getTransitionFromParent();
+            transitionList.add(transition);
+            if (transition instanceof AddPropertyTransition && ((AddPropertyTransition) transition).getProperty().getKey().equals(newProp.getKey())) {
                 found = true;
             }
             top = top.parent;
         }
         ShapeImpl newShape = top;
-        for (ListIterator<Property> iterator = propertyList.listIterator(propertyList.size()); iterator.hasPrevious();) {
-            Property prop = iterator.previous();
-            if (prop.getKey().equals(newProp.getKey())) {
+        for (ListIterator<Transition> iterator = transitionList.listIterator(transitionList.size()); iterator.hasPrevious();) {
+            Transition transition = iterator.previous();
+            if (transition instanceof AddPropertyTransition && ((AddPropertyTransition) transition).getProperty().getKey().equals(newProp.getKey())) {
                 newShape = newShape.addProperty(newProp);
             } else {
-                newShape = newShape.addProperty(prop);
+                newShape = newShape.applyTransition(transition, false);
             }
         }
         return newShape;
@@ -812,14 +826,14 @@
         if (cachedShape != null) {
             return cachedShape;
         } else {
-            ShapeImpl newShape = createShape(layout, sharedData, this, newOps, propertyMap, allocator(), id);
-            addTransition(transition, newShape);
+            ShapeImpl newShape = createShape(layout, sharedData, this, newOps, propertyMap, transition, allocator(), id);
+            addDirectTransition(transition, newShape);
             return newShape;
         }
     }
 
     @Override
-    public final Shape reservePrimitiveExtensionArray() {
+    public final ShapeImpl reservePrimitiveExtensionArray() {
         if (layout.hasPrimitiveExtensionArray() && !hasPrimitiveArray()) {
             return addPrimitiveExtensionArray();
         }