Separating transitions from descriptors.

src/transitions.h

Index: src/transitions.h
diff --git a/src/transitions.h b/src/transitions.h
new file mode 100644
index 0000000000000000000000000000000000000000..0046174b951031efa5d359060ebe68f90942b343
--- /dev/null
+++ b/src/transitions.h
@@ -0,0 +1,164 @@
+// Copyright 2012 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+//       notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+//       copyright notice, this list of conditions and the following
+//       disclaimer in the documentation and/or other materials provided
+//       with the distribution.
+//     * Neither the name of Google Inc. nor the names of its
+//       contributors may be used to endorse or promote products derived
+//       from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#ifndef V8_TRANSITIONS_H_
+#define V8_TRANSITIONS_H_
+
+#include "elements-kind.h"
+#include "heap.h"
+#include "isolate.h"
+#include "objects.h"
+#include "v8checks.h"
+
+namespace v8 {
+namespace internal {
+
+
+// TransitionArrays are fixed arrays used to hold map transitions for property,
+// constant, and element changes.
+// The format of the these objects is:
+// [0] Elements transition
+// [1] First transition
+// [length() - 2] Last transition

[Jakob Kummerow, 2012/06/29 16:31:36]

Is that "length() - 2" because kTransitionSize == 2? In that case, I'd write
"[length() - kTransitionSize]" instead.

[Toon Verwaest, 2012/07/05 12:56:11]

No, the comment was out of date. It's length() - 1, because there's the elements
transition. It'll be - 2 once the prototype transition is in; and - 3 once the
descriptor array is in as well.

On 2012/06/29 16:31:36, Jakob wrote:

+class TransitionArray: public FixedArray {
+ public:
+  inline Map* elements();

[Michael Starzinger, 2012/06/28 16:02:12]

Can we call this elements_transition instead?

[Toon Verwaest, 2012/06/29 08:14:55]

Done.

+  inline void set_elements(
+      Map* value,
+      WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
+  inline void ClearElements();
+  inline bool HasElementsTransition();
+  // Accessors for fetching instance transition at transition number.
+  inline String* GetKey(int transition_number);
+  inline Object** GetKeySlot(int transition_number);

[Jakob Kummerow, 2012/06/29 16:31:36]

Set{Key,Value}Unchecked() -- what do we need these for?

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+  inline void SetKeyUnchecked(Heap* heap, int transition_number, String* value);
+  inline Object* GetValue(int transition_number);
+  inline Object** GetValueSlot(int transition_number);
+  inline void SetValueUnchecked(Heap* heap,
+                                int transition_number,
+                                Object* value);
+  inline Map* GetTargetMap(int transition_number);
+  inline PropertyDetails GetTargetDetails(int transition_number);
+  inline Object** GetElementsSlot();
+  bool TransitionsTo(Object* target);
+
+  // Returns the number of transitions in the array.
+  int number_of_transitions() {
+    ASSERT(length() >= kFirstIndex);
+    int len = length();
+    return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kTransitionSize;
+  }
+
+  inline int number_of_entries() { return number_of_transitions(); }
+
+  // Copy the transition array, inserting a new transition. While adding, they

[Jakob Kummerow, 2012/06/29 16:31:36]

who's "they"?

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+  // must not be removed.  All null transitions are removed.
+  MUST_USE_RESULT MaybeObject* CopyInsert(String* name, Object* map);
+
+  // Copy a single transition from the origin array.
+  inline void CopyFrom(TransitionArray* origin,
+                       int origin_transition,
+                       int target_transition);
+
+  // Search a transition for a given property name.
+  inline int Search(String* name);
+
+  // Allocates a TransitionArray.
+  MUST_USE_RESULT static MaybeObject* Allocate(int number_of_transitions);
+
+  // Casting.
+  static inline TransitionArray* cast(Object* obj);
+
+  // Constant for denoting key was not found.
+  static const int kNotFound = -1;
+
+  static const int kElementsTransitionIndex = 0;
+  static const int kFirstIndex = 1;
+
+  // Layout transition array header.
+  static const int kElementsTransitionOffset = FixedArray::kHeaderSize;
+  static const int kFirstOffset = kElementsTransitionOffset + kPointerSize;
+
+  // Layout of map transition.
+  static const int kTransitionKey = 0;
+  static const int kTransitionValue = 1;
+  static const int kTransitionSize = 2;
+
+#ifdef OBJECT_PRINT
+  // Print all the transitions.
+  inline void PrintTransitions() {
+    PrintTransitions(stdout);
+  }
+  void PrintTransitions(FILE* out);
+#endif
+
+#ifdef DEBUG
+  // Is the transition array sorted and without duplicates?

[Jakob Kummerow, 2012/06/29 16:31:36]

nit: this comment is kinda unnecessary, as it doesn't add information beyond the
function name. Feel free to just drop it. 
(Same for the next two methods.)

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+  bool IsSortedNoDuplicates();
+
+  // Is the transition array consistent with the back pointers in targets?
+  bool IsConsistentWithBackPointers(Map* current_map);
+
+  // Are two TransitionArrays equal?
+  bool IsEqualTo(TransitionArray* other);
+#endif
+
+  // The maximum number of transitions we want in a transition array (should
+  // fit in a page).
+  static const int kMaxNumberOfTransitions = 1024 + 512;
+
+ private:
+  // Conversion from transition number to array indices.
+  static int ToKeyIndex(int transition_number) {
+    return kFirstIndex +
+           (transition_number * kTransitionSize) +
+           kTransitionKey;
+  }
+
+  static int ToValueIndex(int transition_number) {
+    return kFirstIndex +
+           (transition_number * kTransitionSize) +
+           kTransitionValue;
+  }
+
+  inline void Set(int transition_number, String* key, Object* value);
+
+  // Swap operation on FixedArray without using write barriers.
+  static inline void NoIncrementalWriteBarrierSwap(

[Jakob Kummerow, 2012/06/29 16:31:36]

I don't see where this is used. If the intention was to forbid its use, please
indicate that in a comment. (You can remove the uninformative existing comment
in turn.)

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+      FixedArray* array, int first, int second);
+
+  // Swap first and second transition.
+  inline void NoIncrementalWriteBarrierSwapTransitions(

[Jakob Kummerow, 2012/06/29 16:31:36]

I don't see where this is used.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+      int first, int second);
+
+  DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
+};
+
+
+} }  // namespace v8::internal
+
+#endif  // V8_TRANSITIONS_H_