1 /*
2  * Copyright (c) 2021-2024 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/js_thread.h"
23 
24 namespace panda::ecmascript {
GetPropertiesCapacity() const25 inline int LayoutInfo::GetPropertiesCapacity() const
26 {
27     return static_cast<int>((GetLength()) >> ELEMENTS_INDEX_LOG2);
28 }
29 
NumberOfElements() const30 inline int LayoutInfo::NumberOfElements() const
31 {
32     return GetExtraLength();
33 }
34 
SetNumberOfElements([[maybe_unused]] 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) const40 inline uint32_t LayoutInfo::GetKeyIndex(int index) const
41 {
42     return static_cast<uint32_t>(index) << ELEMENTS_INDEX_LOG2;
43 }
44 
GetAttrIndex(int index) const45 inline uint32_t LayoutInfo::GetAttrIndex(int index) const
46 {
47     return (static_cast<uint32_t>(index) << ELEMENTS_INDEX_LOG2) + ATTR_INDEX_OFFSET;
48 }
49 
SetWithoutBarrier(uint32_t idx, const JSTaggedValue &value)50 inline void LayoutInfo::SetWithoutBarrier(uint32_t idx, const JSTaggedValue &value)
51 {
52     ASSERT(idx < GetLength());
53     ASSERT(!value.IsHeapObject());
54     size_t offset = JSTaggedValue::TaggedTypeSize() * idx;
55 
56     Barriers::SetPrimitive<JSTaggedType>(GetData(), offset, value.GetRawData());
57 }
58 
59 inline void LayoutInfo::SetPropertyInit(const JSThread *thread, int index, const JSTaggedValue &key,
60                                         const PropertyAttributes &attr)
61 {
62     uint32_t fixedIdx = GetKeyIndex(index);
63     TaggedArray::Set(thread, fixedIdx, key);
64     TaggedArray::Set(thread, fixedIdx + ATTR_INDEX_OFFSET, attr.GetNormalTagged());
65 }
66 
67 inline void LayoutInfo::SetNormalAttr(const JSThread *thread, int index, const PropertyAttributes &attr)
68 {
69     uint32_t fixedIdx = GetAttrIndex(index);
70     PropertyAttributes oldAttr(TaggedArray::Get(fixedIdx));
71     oldAttr.SetNormalAttr(attr.GetNormalAttr());
72     TaggedArray::Set(thread, fixedIdx, oldAttr.GetTaggedValue());
73 }
74 
75 inline JSTaggedValue LayoutInfo::GetKey(int index) const
76 {
77     uint32_t fixedIdx = GetKeyIndex(index);
78     return TaggedArray::Get(fixedIdx);
79 }
80 
81 inline PropertyAttributes LayoutInfo::GetAttr(int index) const
82 {
83     uint32_t fixedIdx = GetAttrIndex(index);
84     return PropertyAttributes(TaggedArray::Get(fixedIdx));
85 }
86 
87 inline JSTaggedValue LayoutInfo::GetSortedKey(int index) const
88 {
89     uint32_t fixedIdx = GetSortedIndex(index);
90     return GetKey(fixedIdx);
91 }
92 
93 inline uint32_t LayoutInfo::GetSortedIndex(int index) const
94 {
95     return GetAttr(index).GetSortedIndex();
96 }
97 
98 inline void LayoutInfo::SetSortedIndex(const JSThread *thread, int index, int sortedIndex)
99 {
100     uint32_t fixedIdx = GetAttrIndex(index);
101     PropertyAttributes attr(TaggedArray::Get(fixedIdx));
102     attr.SetSortedIndex(sortedIndex);
103     TaggedArray::Set(thread, fixedIdx, attr.GetTaggedValue());
104 }
105 
106 inline int LayoutInfo::FindElementWithCache(const JSThread *thread, JSHClass *cls, JSTaggedValue key,
107                                             int propertiesNumber)
108 {
109     ASSERT(NumberOfElements() >= propertiesNumber);
110     const int MAX_ELEMENTS_LINER_SEARCH = 9; // 9: Builtins Object properties number is nine;
111     if (propertiesNumber <= MAX_ELEMENTS_LINER_SEARCH) {
112         Span<struct Properties> sp(GetProperties(), propertiesNumber);
113         for (int i = 0; i < propertiesNumber; i++) {
114             if (sp[i].key_ == key) {
115                 return i;
116             }
117         }
118         return -1;
119     }
120 
121     // jit compile thread not use cache
122     if (thread->IsJitThread()) {
123         return BinarySearch(key, propertiesNumber);
124     }
125 
126     PropertiesCache *cache = thread->GetPropertiesCache();
127     int index = cache->Get(cls, key);
128     if (index == PropertiesCache::NOT_FOUND) {
129         index = BinarySearch(key, propertiesNumber);
130         if (index != -1) {
131             cache->Set(cls, key, index);
132         }
133     }
134     return index;
135 }
136 
BinarySearch(JSTaggedValue key, int propertiesNumber)137 inline int LayoutInfo::BinarySearch(JSTaggedValue key, int propertiesNumber)
138 {
139     ASSERT(NumberOfElements() >= propertiesNumber);
140     int low = 0;
141     int elements = NumberOfElements();
142     int high = elements - 1;
143     uint32_t keyHash = key.GetKeyHashCode();
144 
145     ASSERT(low <= high);
146 
147     while (low <= high) {
148         int mid = low + (high - low) / 2;  // 2: half
149         JSTaggedValue midKey = GetSortedKey(mid);
150         uint32_t midHash = midKey.GetKeyHashCode();
151         if (midHash > keyHash) {
152             high = mid - 1;
153         } else if (midHash < keyHash) {
154             low = mid + 1;
155         } else {
156             int sortIndex = static_cast<int>(GetSortedIndex(mid));
157             JSTaggedValue currentKey = GetKey(sortIndex);
158             if (currentKey == key) {
159                 return sortIndex < propertiesNumber ? sortIndex : -1;
160             }
161             int midLeft = mid;
162             int midRight = mid;
163             while (midLeft - 1 >= 0) {
164                 sortIndex = static_cast<int>(GetSortedIndex(--midLeft));
165                 currentKey = GetKey(sortIndex);
166                 if (currentKey.GetKeyHashCode() == keyHash) {
167                     if (currentKey == key) {
168                         return sortIndex < propertiesNumber ? sortIndex : -1;
169                     }
170                 } else {
171                     break;
172                 }
173             }
174             while (midRight + 1 < elements) {
175                 sortIndex = static_cast<int>(GetSortedIndex(++midRight));
176                 currentKey = GetKey(sortIndex);
177                 if (currentKey.GetKeyHashCode() == keyHash) {
178                     if (currentKey == key) {
179                         return sortIndex < propertiesNumber ? sortIndex : -1;
180                     }
181                 } else {
182                     break;
183                 }
184             }
185             return -1;
186         }
187     }
188     return -1;
189 }
190 
SetIsNotHole(const JSThread *thread, int index)191 inline void LayoutInfo::SetIsNotHole(const JSThread *thread, int index)
192 {
193     uint32_t fixedIdx = GetAttrIndex(index);
194     PropertyAttributes attr(TaggedArray::Get(fixedIdx));
195     attr.SetIsNotHole(true);
196     TaggedArray::Set(thread, fixedIdx, attr.GetTaggedValue());
197 }
198 
UpdateTrackTypeAttr(int index, const PropertyAttributes &attr)199 inline void LayoutInfo::UpdateTrackTypeAttr(int index, const PropertyAttributes &attr)
200 {
201     uint32_t fixedIdx = GetAttrIndex(index);
202     PropertyAttributes oldAttr(TaggedArray::Get(fixedIdx));
203     oldAttr.SetNormalAttr(attr.GetNormalAttr());
204     oldAttr.SetIsPGODumped(false);
205     SetWithoutBarrier(fixedIdx, oldAttr.GetTaggedValue());
206 }
207 
SetIsPGODumped(int index)208 inline void LayoutInfo::SetIsPGODumped(int index)
209 {
210     uint32_t fixedIdx = GetAttrIndex(index);
211     PropertyAttributes attr(TaggedArray::Get(fixedIdx));
212     attr.SetIsPGODumped(true);
213     SetWithoutBarrier(fixedIdx, attr.GetTaggedValue());
214 }
215 
216 template<bool checkDuplicateKeys /* = false*/>
AddKey(const JSThread *thread, [[maybe_unused]] int index, const JSTaggedValue &key, const PropertyAttributes &attr)217 void LayoutInfo::AddKey(const JSThread *thread, [[maybe_unused]] int index, const JSTaggedValue &key,
218                         const PropertyAttributes &attr)
219 {
220     DISALLOW_GARBAGE_COLLECTION;
221     int number = NumberOfElements();
222     ASSERT(attr.GetOffset() == static_cast<uint32_t>(number));
223     ASSERT(number + 1 <= GetPropertiesCapacity());
224     ASSERT(number == index);
225     SetNumberOfElements(thread, number + 1);
226     SetPropertyInit(thread, number, key, attr);
227 
228     uint32_t keyHash = key.GetKeyHashCode();
229     int insertIndex = number;
230     for (; insertIndex > 0; --insertIndex) {
231         JSTaggedValue prevKey = GetSortedKey(insertIndex - 1);
232         if (prevKey.GetKeyHashCode() <= keyHash) {
233             break;
234         }
235         SetSortedIndex(thread, insertIndex, GetSortedIndex(insertIndex - 1));
236     }
237     SetSortedIndex(thread, insertIndex, number);
238     if constexpr (checkDuplicateKeys) {
239         while (insertIndex > 0) {
240             JSTaggedValue prevKey = GetSortedKey(--insertIndex);
241             if (prevKey.GetKeyHashCode() < keyHash) {
242                 return;
243             }
244             if (prevKey == key) {
245                 THROW_TYPE_ERROR(const_cast<JSThread *>(thread), "property keys can not duplicate");
246             }
247         }
248     }
249 }
250 }  // namespace panda::ecmascript
251 #endif  // ECMASCRIPT_LAYOUT_INFO_INL_H
252