1 /*
2 * Copyright (c) 2021 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #ifndef ECMASCRIPT_LAYOUT_INFO_INL_H
17 #define ECMASCRIPT_LAYOUT_INFO_INL_H
18
19 #include "ecmascript/layout_info.h"
20
21 #include "ecmascript/ic/properties_cache.h"
22 #include "ecmascript/tagged_array-inl.h"
23
24 namespace panda::ecmascript {
GetPropertiesCapacity()25 inline int LayoutInfo::GetPropertiesCapacity() const
26 {
27 return static_cast<int>((GetLength()) >> ELEMENTS_INDEX_LOG2);
28 }
29
NumberOfElements()30 inline int LayoutInfo::NumberOfElements() const
31 {
32 return GetExtraLength();
33 }
34
SetNumberOfElements(const JSThread * thread,int properties)35 inline void LayoutInfo::SetNumberOfElements([[maybe_unused]] const JSThread *thread, int properties)
36 {
37 SetExtraLength(properties);
38 }
39
GetKeyIndex(int index)40 inline uint32_t LayoutInfo::GetKeyIndex(int index) const
41 {
42 return static_cast<uint32_t>(index) << ELEMENTS_INDEX_LOG2;
43 }
44
GetAttrIndex(int index)45 inline uint32_t LayoutInfo::GetAttrIndex(int index) const
46 {
47 return (static_cast<uint32_t>(index) << ELEMENTS_INDEX_LOG2) + ATTR_INDEX_OFFSET;
48 }
49
SetPropertyInit(const JSThread * thread,int index,const JSTaggedValue & key,const PropertyAttributes & attr)50 inline void LayoutInfo::SetPropertyInit(const JSThread *thread, int index, const JSTaggedValue &key,
51 const PropertyAttributes &attr)
52 {
53 uint32_t fixedIdx = GetKeyIndex(index);
54 TaggedArray::Set(thread, fixedIdx, key);
55 TaggedArray::Set(thread, fixedIdx + ATTR_INDEX_OFFSET, attr.GetNormalTagged());
56 }
57
SetNormalAttr(const JSThread * thread,int index,const PropertyAttributes & attr)58 inline void LayoutInfo::SetNormalAttr(const JSThread *thread, int index, const PropertyAttributes &attr)
59 {
60 uint32_t fixedIdx = GetAttrIndex(index);
61 PropertyAttributes oldAttr(TaggedArray::Get(fixedIdx));
62 oldAttr.SetNormalAttr(attr.GetNormalAttr());
63 TaggedArray::Set(thread, fixedIdx, oldAttr.GetTaggedValue());
64 }
65
GetKey(int index)66 inline JSTaggedValue LayoutInfo::GetKey(int index) const
67 {
68 uint32_t fixedIdx = GetKeyIndex(index);
69 return TaggedArray::Get(fixedIdx);
70 }
71
GetAttr(int index)72 inline PropertyAttributes LayoutInfo::GetAttr(int index) const
73 {
74 uint32_t fixedIdx = GetAttrIndex(index);
75 return PropertyAttributes(TaggedArray::Get(fixedIdx));
76 }
77
GetSortedKey(int index)78 inline JSTaggedValue LayoutInfo::GetSortedKey(int index) const
79 {
80 uint32_t fixedIdx = GetSortedIndex(index);
81 return GetKey(fixedIdx);
82 }
83
GetSortedIndex(int index)84 inline uint32_t LayoutInfo::GetSortedIndex(int index) const
85 {
86 return GetAttr(index).GetSortedIndex();
87 }
88
SetSortedIndex(const JSThread * thread,int index,int sortedIndex)89 inline void LayoutInfo::SetSortedIndex(const JSThread *thread, int index, int sortedIndex)
90 {
91 uint32_t fixedIdx = GetAttrIndex(index);
92 PropertyAttributes attr(TaggedArray::Get(fixedIdx));
93 attr.SetSortedIndex(sortedIndex);
94 TaggedArray::Set(thread, fixedIdx, attr.GetTaggedValue());
95 }
96
FindElementWithCache(const JSThread * thread,JSHClass * cls,JSTaggedValue key,int propertiesNumber)97 inline int LayoutInfo::FindElementWithCache(const JSThread *thread, JSHClass *cls, JSTaggedValue key,
98 int propertiesNumber)
99 {
100 ASSERT(NumberOfElements() >= propertiesNumber);
101 const int MAX_ELEMENTS_LINER_SEARCH = 9; // 9: Builtins Object properties number is nine;
102 if (propertiesNumber <= MAX_ELEMENTS_LINER_SEARCH) {
103 Span<struct Properties> sp(GetProperties(), propertiesNumber);
104 for (int i = 0; i < propertiesNumber; i++) {
105 if (sp[i].key_ == key) {
106 return i;
107 }
108 }
109 return -1;
110 }
111
112 PropertiesCache *cache = thread->GetPropertiesCache();
113 int index = cache->Get(cls, key);
114 if (index == PropertiesCache::NOT_FOUND) {
115 index = BinarySearch(key, propertiesNumber);
116 if (index != -1) {
117 cache->Set(cls, key, index);
118 }
119 }
120 return index;
121 }
122
BinarySearch(JSTaggedValue key,int propertiesNumber)123 inline int LayoutInfo::BinarySearch(JSTaggedValue key, int propertiesNumber)
124 {
125 ASSERT(NumberOfElements() >= propertiesNumber);
126 int low = 0;
127 int elements = NumberOfElements();
128 int high = elements - 1;
129 uint32_t keyHash = key.GetKeyHashCode();
130
131 ASSERT(low <= high);
132
133 while (low <= high) {
134 int mid = low + (high - low) / 2; // 2: half
135 JSTaggedValue midKey = GetSortedKey(mid);
136 uint32_t midHash = midKey.GetKeyHashCode();
137 if (midHash > keyHash) {
138 high = mid - 1;
139 } else if (midHash < keyHash) {
140 low = mid + 1;
141 } else {
142 int sortIndex = static_cast<int>(GetSortedIndex(mid));
143 JSTaggedValue currentKey = GetKey(sortIndex);
144 if (currentKey == key) {
145 return sortIndex < propertiesNumber ? sortIndex : -1;
146 }
147 int midLeft = mid;
148 int midRight = mid;
149 while (midLeft - 1 >= 0) {
150 sortIndex = static_cast<int>(GetSortedIndex(--midLeft));
151 currentKey = GetKey(sortIndex);
152 if (currentKey.GetKeyHashCode() == keyHash) {
153 if (currentKey == key) {
154 return sortIndex < propertiesNumber ? sortIndex : -1;
155 }
156 } else {
157 break;
158 }
159 }
160 while (midRight + 1 < elements) {
161 sortIndex = static_cast<int>(GetSortedIndex(++midRight));
162 currentKey = GetKey(sortIndex);
163 if (currentKey.GetKeyHashCode() == keyHash) {
164 if (currentKey == key) {
165 return sortIndex < propertiesNumber ? sortIndex : -1;
166 }
167 } else {
168 break;
169 }
170 }
171 return -1;
172 }
173 }
174 return -1;
175 }
176
SetIsNotHole(const JSThread * thread,int index)177 inline void LayoutInfo::SetIsNotHole(const JSThread *thread, int index)
178 {
179 uint32_t fixedIdx = GetAttrIndex(index);
180 PropertyAttributes attr(TaggedArray::Get(fixedIdx));
181 attr.SetIsNotHole(true);
182 TaggedArray::Set(thread, fixedIdx, attr.GetTaggedValue());
183 }
184
185
186 template<bool checkDuplicateKeys /* = false*/>
AddKey(const JSThread * thread,int index,const JSTaggedValue & key,const PropertyAttributes & attr)187 void LayoutInfo::AddKey(const JSThread *thread, [[maybe_unused]] int index, const JSTaggedValue &key,
188 const PropertyAttributes &attr)
189 {
190 DISALLOW_GARBAGE_COLLECTION;
191 int number = NumberOfElements();
192 ASSERT(attr.GetOffset() == static_cast<uint32_t>(number));
193 ASSERT(number + 1 <= GetPropertiesCapacity());
194 ASSERT(number == index);
195 SetNumberOfElements(thread, number + 1);
196 SetPropertyInit(thread, number, key, attr);
197
198 uint32_t keyHash = key.GetKeyHashCode();
199 int insertIndex = number;
200 for (; insertIndex > 0; --insertIndex) {
201 JSTaggedValue prevKey = GetSortedKey(insertIndex - 1);
202 if (prevKey.GetKeyHashCode() <= keyHash) {
203 break;
204 }
205 SetSortedIndex(thread, insertIndex, GetSortedIndex(insertIndex - 1));
206 }
207 SetSortedIndex(thread, insertIndex, number);
208 if (checkDuplicateKeys) {
209 while (insertIndex > 0) {
210 JSTaggedValue prevKey = GetSortedKey(--insertIndex);
211 if (prevKey.GetKeyHashCode() < keyHash) {
212 return;
213 }
214 if (prevKey == key) {
215 THROW_TYPE_ERROR(const_cast<JSThread *>(thread), "property keys can not duplicate");
216 }
217 }
218 }
219 }
220 } // namespace panda::ecmascript
221 #endif // ECMASCRIPT_LAYOUT_INFO_INL_H
222