dd419923c2951b06f55eeb98f7f7519fdea695c6
[WebKit.git] / JavaScriptCore / kjs / StructureID.cpp
1 /*
2  * Copyright (C) 2008 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "StructureID.h"
28
29 #include "identifier.h"
30 #include "JSObject.h"
31 #include "PropertyNameArray.h"
32 #include "lookup.h"
33 #include <wtf/RefPtr.h>
34
35 using namespace std;
36
37 namespace JSC {
38
39 StructureID::StructureID(JSValue* prototype, const TypeInfo& typeInfo)
40     : m_typeInfo(typeInfo)
41     , m_isDictionary(false)
42     , m_prototype(prototype)
43     , m_cachedPrototypeChain(0)
44     , m_previous(0)
45     , m_nameInPrevious(0)
46     , m_transitionCount(0)
47     , m_cachedTransistionOffset(WTF::notFound)
48 {
49     ASSERT(m_prototype);
50     ASSERT(m_prototype->isObject() || m_prototype->isNull());
51 }
52
53 void StructureID::getEnumerablePropertyNames(ExecState* exec, PropertyNameArray& propertyNames, JSObject* baseObject)
54 {
55     bool shouldCache = !(propertyNames.size() || m_isDictionary);
56
57     if (shouldCache && m_cachedPropertyNameArrayData) {
58         if (structureIDChainsAreEqual(m_cachedPropertyNameArrayData->cachedPrototypeChain(), cachedPrototypeChain())) {
59             propertyNames.setData(m_cachedPropertyNameArrayData);
60             return;
61         }
62     }
63
64     m_propertyMap.getEnumerablePropertyNames(propertyNames);
65
66     // Add properties from the static hashtables of properties
67     for (const ClassInfo* info = baseObject->classInfo(); info; info = info->parentClass) {
68         const HashTable* table = info->propHashTable(exec);
69         if (!table)
70             continue;
71         table->initializeIfNeeded(exec);
72         ASSERT(table->table);
73         int hashSizeMask = table->hashSizeMask;
74         const HashEntry* entry = table->table;
75         for (int i = 0; i <= hashSizeMask; ++i, ++entry) {
76             if (entry->key() && !(entry->attributes() & DontEnum))
77                 propertyNames.add(entry->key());
78         }
79     }
80
81     if (m_prototype->isObject())
82         static_cast<JSObject*>(m_prototype)->getPropertyNames(exec, propertyNames);
83
84     if (shouldCache) {
85         if (m_cachedPropertyNameArrayData)
86             m_cachedPropertyNameArrayData->setCachedStructureID(0);
87
88         m_cachedPropertyNameArrayData = propertyNames.data();
89
90         StructureIDChain* chain = cachedPrototypeChain();
91         if (!chain)
92             chain = createCachedPrototypeChain();
93         m_cachedPropertyNameArrayData->setCachedPrototypeChain(chain);
94         m_cachedPropertyNameArrayData->setCachedStructureID(this);
95     }
96 }
97
98 void StructureID::clearEnumerationCache()
99 {
100     if (m_cachedPropertyNameArrayData)
101         m_cachedPropertyNameArrayData->setCachedStructureID(0);
102     m_cachedPropertyNameArrayData.clear();
103 }
104
105 void StructureID::transitionTo(StructureID* oldStructureID, StructureID* newStructureID, JSObject* slotBase)
106 {
107     if (!slotBase->usingInlineStorage() && oldStructureID->m_propertyMap.size() != newStructureID->m_propertyMap.size())
108         slotBase->allocatePropertyStorage(oldStructureID->m_propertyMap.size(), newStructureID->m_propertyMap.size());
109 }
110
111 PassRefPtr<StructureID> StructureID::addPropertyTransition(StructureID* structureID, const Identifier& propertyName, JSValue* value, unsigned attributes, JSObject* slotBase, PutPropertySlot& slot, PropertyStorage& propertyStorage)
112 {
113     ASSERT(!structureID->m_isDictionary);
114     ASSERT(structureID->typeInfo().type() == ObjectType);
115
116     if (StructureID* existingTransition = structureID->m_transitionTable.get(make_pair(propertyName.ustring().rep(), attributes))) {
117         if (!slotBase->usingInlineStorage() && structureID->m_propertyMap.size() != existingTransition->m_propertyMap.size())
118             slotBase->allocatePropertyStorage(structureID->m_propertyMap.size(), existingTransition->m_propertyMap.size());
119
120         size_t offset = existingTransition->cachedTransistionOffset();
121         ASSERT(offset != WTF::notFound);
122         propertyStorage[offset] = value;
123         slot.setNewProperty(slotBase, offset);
124
125         return existingTransition;
126     }
127
128     if (structureID->m_transitionCount > s_maxTransitionLength) {
129         RefPtr<StructureID> transition = toDictionaryTransition(structureID);
130         transition->m_propertyMap.put(propertyName, value, attributes, false, slotBase, slot, propertyStorage);
131         return transition.release();
132     }
133
134     RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo());
135     transition->m_cachedPrototypeChain = structureID->m_cachedPrototypeChain;
136     transition->m_previous = structureID;
137     transition->m_nameInPrevious = propertyName.ustring().rep();
138     transition->m_attributesInPrevious = attributes;
139     transition->m_transitionCount = structureID->m_transitionCount + 1;
140     transition->m_propertyMap = structureID->m_propertyMap;
141
142     size_t offset = transition->m_propertyMap.put(propertyName, value, attributes, false, slotBase, slot, propertyStorage);
143     transition->setCachedTransistionOffset(offset);
144
145     structureID->m_transitionTable.add(make_pair(propertyName.ustring().rep(), attributes), transition.get());
146     return transition.release();
147 }
148
149 PassRefPtr<StructureID> StructureID::toDictionaryTransition(StructureID* structureID)
150 {
151     ASSERT(!structureID->m_isDictionary);
152
153     RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo());
154     transition->m_isDictionary = true;
155     transition->m_propertyMap = structureID->m_propertyMap;
156     return transition.release();
157 }
158
159 PassRefPtr<StructureID> StructureID::fromDictionaryTransition(StructureID* structureID)
160 {
161     ASSERT(structureID->m_isDictionary);
162
163     // Since dictionary StructureIDs are not shared, and no opcodes specialize
164     // for them, we don't need to allocate a new StructureID when transitioning
165     // to non-dictionary status.
166     structureID->m_isDictionary = false;
167     return structureID;
168 }
169
170 PassRefPtr<StructureID> StructureID::changePrototypeTransition(StructureID* structureID, JSValue* prototype)
171 {
172     RefPtr<StructureID> transition = create(prototype, structureID->typeInfo());
173     transition->m_transitionCount = structureID->m_transitionCount + 1;
174     transition->m_propertyMap = structureID->m_propertyMap;
175     return transition.release();
176 }
177
178 PassRefPtr<StructureID> StructureID::getterSetterTransition(StructureID* structureID)
179 {
180     RefPtr<StructureID> transition = create(structureID->storedPrototype(), structureID->typeInfo());
181     transition->m_transitionCount = structureID->m_transitionCount + 1;
182     transition->m_propertyMap = structureID->m_propertyMap;
183     return transition.release();
184 }
185
186 StructureID::~StructureID()
187 {
188     if (m_previous) {
189         ASSERT(m_previous->m_transitionTable.contains(make_pair(m_nameInPrevious, m_attributesInPrevious)));
190         m_previous->m_transitionTable.remove(make_pair(m_nameInPrevious, m_attributesInPrevious));
191     }
192
193     if (m_cachedPropertyNameArrayData)
194         m_cachedPropertyNameArrayData->setCachedStructureID(0);
195 }
196
197 StructureIDChain* StructureID::createCachedPrototypeChain()
198 {
199     ASSERT(typeInfo().type() == ObjectType);
200     ASSERT(!m_cachedPrototypeChain);
201
202     JSValue* prototype = storedPrototype();
203     if (JSImmediate::isImmediate(prototype))
204         return 0;
205
206     RefPtr<StructureIDChain> chain = StructureIDChain::create(static_cast<JSObject*>(prototype)->structureID());
207     setCachedPrototypeChain(chain.release());
208     return cachedPrototypeChain();
209 }
210
211 StructureIDChain::StructureIDChain(StructureID* structureID)
212 {
213     size_t size = 1;
214
215     StructureID* tmp = structureID;
216     while (!tmp->storedPrototype()->isNull()) {
217         ++size;
218         tmp = static_cast<JSCell*>(tmp->storedPrototype())->structureID();
219     }
220     
221     m_vector.set(new RefPtr<StructureID>[size + 1]);
222
223     size_t i;
224     for (i = 0; i < size - 1; ++i) {
225         m_vector[i] = structureID;
226         structureID = static_cast<JSObject*>(structureID->storedPrototype())->structureID();
227     }
228     m_vector[i] = structureID;
229     m_vector[i + 1] = 0;
230 }
231
232 bool structureIDChainsAreEqual(StructureIDChain* chainA, StructureIDChain* chainB)
233 {
234     if (!chainA || !chainB)
235         return false;
236
237     RefPtr<StructureID>* a = chainA->head();
238     RefPtr<StructureID>* b = chainB->head();
239     while (1) {
240         if (*a != *b)
241             return false;
242         if (!*a)
243             return true;
244         a++;
245         b++;
246     }
247 }
248
249 } // namespace JSC