199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// Copyright 2012 the V8 project authors. All rights reserved. 299aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// Redistribution and use in source and binary forms, with or without 399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// modification, are permitted provided that the following conditions are 499aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// met: 599aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// 699aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// * Redistributions of source code must retain the above copyright 799aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// notice, this list of conditions and the following disclaimer. 899aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// * Redistributions in binary form must reproduce the above 999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// copyright notice, this list of conditions and the following 1099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// disclaimer in the documentation and/or other materials provided 1199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// with the distribution. 1299aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// * Neither the name of Google Inc. nor the names of its 1399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// contributors may be used to endorse or promote products derived 1499aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// from this software without specific prior written permission. 1599aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// 1699aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1799aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1899aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2299aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2499aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2599aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2699aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2799aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 2899aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#ifndef V8_TRANSITIONS_H_ 2999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#define V8_TRANSITIONS_H_ 3099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 3199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#include "elements-kind.h" 3299aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#include "heap.h" 3399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#include "isolate.h" 3499aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#include "objects.h" 3599aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#include "v8checks.h" 3699aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 3799aa490225c81012235659d9a183226b286178c8yangguo@chromium.orgnamespace v8 { 3899aa490225c81012235659d9a183226b286178c8yangguo@chromium.orgnamespace internal { 3999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 4099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 4199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// TransitionArrays are fixed arrays used to hold map transitions for property, 4289e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org// constant, and element changes. They can either be simple transition arrays 4389e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org// that store a single property transition, or a full transition array that has 44d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org// prototype transitions and multiple property transitons. The details related 45d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org// to property transitions are accessed in the descriptor array of the target 46d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org// map. In the case of a simple transition, the key is also read from the 47d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org// descriptor array of the target map. 4889e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org// 4989e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org// The simple format of the these objects is: 5089e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org// [0] Undefined or back pointer map 5189e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org// [1] Single transition 5289e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org// 5389e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org// The full format is: 5489e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org// [0] Undefined or back pointer map 55d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org// [1] Smi(0) or fixed array of prototype transitions 56d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org// [2] First transition 5799aa490225c81012235659d9a183226b286178c8yangguo@chromium.org// [length() - kTransitionSize] Last transition 5899aa490225c81012235659d9a183226b286178c8yangguo@chromium.orgclass TransitionArray: public FixedArray { 5999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org public: 6099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // Accessors for fetching instance transition at transition number. 61750145ab1b720c97adf2b548cc8fbd28c8b8e06dulan@chromium.org inline Name* GetKey(int transition_number); 62750145ab1b720c97adf2b548cc8fbd28c8b8e06dulan@chromium.org inline void SetKey(int transition_number, Name* value); 6381cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org inline Object** GetKeySlot(int transition_number); 6446839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org int GetSortedKeyIndex(int transition_number) { return transition_number; } 6546839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org 66750145ab1b720c97adf2b548cc8fbd28c8b8e06dulan@chromium.org Name* GetSortedKey(int transition_number) { 6746839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org return GetKey(transition_number); 6846839fbbdee40a3d2d924e8b5b13c4139b0b24f2yangguo@chromium.org } 6981cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org 70753aee4dcf0868130789b5af7c1eeb6ab2ab24f9verwaest@chromium.org inline Map* GetTarget(int transition_number); 71753aee4dcf0868130789b5af7c1eeb6ab2ab24f9verwaest@chromium.org inline void SetTarget(int transition_number, Map* target); 7281cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org 7399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org inline PropertyDetails GetTargetDetails(int transition_number); 7481cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org 7581cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org inline bool HasElementsTransition(); 7681cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org 77de64f721c489207a7b9018406d39c7fb04bb9424verwaest@chromium.org inline Object* back_pointer_storage(); 78de64f721c489207a7b9018406d39c7fb04bb9424verwaest@chromium.org inline void set_back_pointer_storage( 79de64f721c489207a7b9018406d39c7fb04bb9424verwaest@chromium.org Object* back_pointer, 80de64f721c489207a7b9018406d39c7fb04bb9424verwaest@chromium.org WriteBarrierMode mode = UPDATE_WRITE_BARRIER); 81de64f721c489207a7b9018406d39c7fb04bb9424verwaest@chromium.org 8281cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org inline FixedArray* GetPrototypeTransitions(); 8381cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org inline void SetPrototypeTransitions( 8481cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org FixedArray* prototype_transitions, 8581cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org WriteBarrierMode mode = UPDATE_WRITE_BARRIER); 8681cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org inline Object** GetPrototypeTransitionsSlot(); 8781cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org inline bool HasPrototypeTransitions(); 8881cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org inline HeapObject* UncheckedPrototypeTransitions(); 8999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 9099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // Returns the number of transitions in the array. 9199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org int number_of_transitions() { 9233e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org if (IsSimpleTransition()) return 1; 9399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org int len = length(); 9499aa490225c81012235659d9a183226b286178c8yangguo@chromium.org return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kTransitionSize; 9599aa490225c81012235659d9a183226b286178c8yangguo@chromium.org } 9699aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 9799aa490225c81012235659d9a183226b286178c8yangguo@chromium.org inline int number_of_entries() { return number_of_transitions(); } 9899aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 9999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // Allocate a new transition array with a single entry. 10006ab2ec756e44eeaf7500b9794f9d2abc79dc8cfverwaest@chromium.org static MUST_USE_RESULT MaybeObject* NewWith( 10133e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org SimpleTransitionFlag flag, 102750145ab1b720c97adf2b548cc8fbd28c8b8e06dulan@chromium.org Name* key, 10306ab2ec756e44eeaf7500b9794f9d2abc79dc8cfverwaest@chromium.org Map* target, 10406ab2ec756e44eeaf7500b9794f9d2abc79dc8cfverwaest@chromium.org Object* back_pointer); 10556c14afabc547f0a8ab2e24d789c00030f8df892ulan@chromium.org 10633e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org MUST_USE_RESULT MaybeObject* ExtendToFullTransitionArray(); 10733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 10899aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // Copy the transition array, inserting a new transition. 10999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // TODO(verwaest): This should not cause an existing transition to be 11099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // overwritten. 111750145ab1b720c97adf2b548cc8fbd28c8b8e06dulan@chromium.org MUST_USE_RESULT MaybeObject* CopyInsert(Name* name, Map* target); 11299aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 11399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // Copy a single transition from the origin array. 11456c14afabc547f0a8ab2e24d789c00030f8df892ulan@chromium.org inline void NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin, 11556c14afabc547f0a8ab2e24d789c00030f8df892ulan@chromium.org int origin_transition, 11656c14afabc547f0a8ab2e24d789c00030f8df892ulan@chromium.org int target_transition); 11799aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 11899aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // Search a transition for a given property name. 119750145ab1b720c97adf2b548cc8fbd28c8b8e06dulan@chromium.org inline int Search(Name* name); 12099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 12199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // Allocates a TransitionArray. 122c1956679bbba3170352a8cc735e8218f9dbe6867jkummerow@chromium.org MUST_USE_RESULT static MaybeObject* Allocate(int number_of_transitions); 12356c14afabc547f0a8ab2e24d789c00030f8df892ulan@chromium.org 124d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org bool IsSimpleTransition() { 125d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org return length() == kSimpleTransitionSize && 126d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org get(kSimpleTransitionTarget)->IsHeapObject() && 127d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org // The IntrusivePrototypeTransitionIterator may have set the map of the 128d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org // prototype transitions array to a smi. In that case, there are 129d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org // prototype transitions, hence this transition array is a full 130d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org // transition array. 131d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org HeapObject::cast(get(kSimpleTransitionTarget))->map()->IsMap() && 132d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org get(kSimpleTransitionTarget)->IsMap(); 133d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org } 134d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org 135d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org bool IsFullTransitionArray() { 136d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org return length() > kFirstIndex || 137d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org (length() == kFirstIndex && !IsSimpleTransition()); 138d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org } 13933e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 14099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // Casting. 14199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org static inline TransitionArray* cast(Object* obj); 14299aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 14399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // Constant for denoting key was not found. 14499aa490225c81012235659d9a183226b286178c8yangguo@chromium.org static const int kNotFound = -1; 14599aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 14689e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org static const int kBackPointerStorageIndex = 0; 14733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 14833e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org // Layout for full transition arrays. 149d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org static const int kPrototypeTransitionsIndex = 1; 150d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org static const int kFirstIndex = 2; 15199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 15233e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org // Layout for simple transition arrays. 15389e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org static const int kSimpleTransitionTarget = 1; 15489e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org static const int kSimpleTransitionSize = 2; 15533e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org static const int kSimpleTransitionIndex = 0; 15633e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org STATIC_ASSERT(kSimpleTransitionIndex != kNotFound); 15733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 15889e18f5599cb4cd462cb1ed324addd7388fb4d60rossberg@chromium.org static const int kBackPointerStorageOffset = FixedArray::kHeaderSize; 15933e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 16033e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org // Layout for the full transition array header. 161d3c42109e5b85232d19beab8deeb24bdcbbf07f9danno@chromium.org static const int kPrototypeTransitionsOffset = kBackPointerStorageOffset + 16281cac2ba397bd57f2967c8b4b677bef08a869991danno@chromium.org kPointerSize; 16399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 16433e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org // Layout of map transition entries in full transition arrays. 16599aa490225c81012235659d9a183226b286178c8yangguo@chromium.org static const int kTransitionKey = 0; 166753aee4dcf0868130789b5af7c1eeb6ab2ab24f9verwaest@chromium.org static const int kTransitionTarget = 1; 16799aa490225c81012235659d9a183226b286178c8yangguo@chromium.org static const int kTransitionSize = 2; 16899aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 16999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#ifdef OBJECT_PRINT 17099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // Print all the transitions. 17199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org inline void PrintTransitions() { 17299aa490225c81012235659d9a183226b286178c8yangguo@chromium.org PrintTransitions(stdout); 17399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org } 17499aa490225c81012235659d9a183226b286178c8yangguo@chromium.org void PrintTransitions(FILE* out); 17599aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#endif 17699aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 17799aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#ifdef DEBUG 17806ab2ec756e44eeaf7500b9794f9d2abc79dc8cfverwaest@chromium.org bool IsSortedNoDuplicates(int valid_entries = -1); 17999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org bool IsConsistentWithBackPointers(Map* current_map); 18099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org bool IsEqualTo(TransitionArray* other); 18199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#endif 18299aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 18399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // The maximum number of transitions we want in a transition array (should 18499aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // fit in a page). 18599aa490225c81012235659d9a183226b286178c8yangguo@chromium.org static const int kMaxNumberOfTransitions = 1024 + 512; 18699aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 18799aa490225c81012235659d9a183226b286178c8yangguo@chromium.org private: 18899aa490225c81012235659d9a183226b286178c8yangguo@chromium.org // Conversion from transition number to array indices. 18999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org static int ToKeyIndex(int transition_number) { 19099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org return kFirstIndex + 19199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org (transition_number * kTransitionSize) + 19299aa490225c81012235659d9a183226b286178c8yangguo@chromium.org kTransitionKey; 19399aa490225c81012235659d9a183226b286178c8yangguo@chromium.org } 19499aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 195753aee4dcf0868130789b5af7c1eeb6ab2ab24f9verwaest@chromium.org static int ToTargetIndex(int transition_number) { 19699aa490225c81012235659d9a183226b286178c8yangguo@chromium.org return kFirstIndex + 19799aa490225c81012235659d9a183226b286178c8yangguo@chromium.org (transition_number * kTransitionSize) + 198753aee4dcf0868130789b5af7c1eeb6ab2ab24f9verwaest@chromium.org kTransitionTarget; 19999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org } 20099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 20156c14afabc547f0a8ab2e24d789c00030f8df892ulan@chromium.org inline void NoIncrementalWriteBarrierSet(int transition_number, 202750145ab1b720c97adf2b548cc8fbd28c8b8e06dulan@chromium.org Name* key, 20356c14afabc547f0a8ab2e24d789c00030f8df892ulan@chromium.org Map* target); 20499aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 20599aa490225c81012235659d9a183226b286178c8yangguo@chromium.org DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray); 20699aa490225c81012235659d9a183226b286178c8yangguo@chromium.org}; 20799aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 20899aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 20999aa490225c81012235659d9a183226b286178c8yangguo@chromium.org} } // namespace v8::internal 21099aa490225c81012235659d9a183226b286178c8yangguo@chromium.org 21199aa490225c81012235659d9a183226b286178c8yangguo@chromium.org#endif // V8_TRANSITIONS_H_ 212