1 /*
2 * Copyright (c) 2022 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 #include "ecmascript/ecma_vm.h"
17 #include "ecmascript/js_symbol.h"
18 #include "ecmascript/object_factory.h"
19 #include "ecmascript/property_attributes.h"
20 #include "ecmascript/tagged_hash_table.h"
21 #include "ecmascript/tests/test_helper.h"
22 #include "ecmascript/transitions_dictionary.h"
23
24 using namespace panda::ecmascript;
25
26 namespace panda::test {
27 class TransitionsDictionaryTest : public BaseTestWithScope<false> {
28 };
29
HWTEST_F_L0(TransitionsDictionaryTest,IsMatch)30 HWTEST_F_L0(TransitionsDictionaryTest, IsMatch)
31 {
32 JSHandle<JSTaggedValue> key(thread, JSTaggedValue::True());
33 JSHandle<JSTaggedValue> otherKey(thread, JSTaggedValue::False());
34 JSHandle<JSTaggedValue> metaData(thread, JSTaggedValue::Undefined());
35 JSHandle<JSTaggedValue> otherDetails(thread, JSTaggedValue::Null());
36 bool result = TransitionsDictionary::IsMatch(key.GetTaggedValue(), metaData.GetTaggedValue(),
37 otherKey.GetTaggedValue(), otherDetails.GetTaggedValue());
38 EXPECT_FALSE(result);
39
40 result = TransitionsDictionary::IsMatch(key.GetTaggedValue(), metaData.GetTaggedValue(),
41 key.GetTaggedValue(), metaData.GetTaggedValue());
42 EXPECT_TRUE(result);
43 }
44
HWTEST_F_L0(TransitionsDictionaryTest,Hash)45 HWTEST_F_L0(TransitionsDictionaryTest, Hash)
46 {
47 auto vm = thread->GetEcmaVM();
48 auto factory = vm->GetFactory();
49
50 // test when key is string.
51 JSHandle<JSTaggedValue> key1(factory->NewFromStdString("k"));
52 JSHandle<JSTaggedValue> metaData1(thread, JSTaggedValue(1)); // test metaData : 1
53 int hash = TransitionsDictionary::Hash(key1.GetTaggedValue(), metaData1.GetTaggedValue());
54 // "k" : 107, hashSeed : 0, shift : 5, metaData : 1
55 EXPECT_EQ(hash, 108); // 108 : (0 << 5) - 0 + 107 + 1
56
57 JSHandle<JSTaggedValue> key2(factory->NewFromStdString("key"));
58 hash = TransitionsDictionary::Hash(key2.GetTaggedValue(), metaData1.GetTaggedValue());
59 EXPECT_EQ(hash, 106080);
60
61 // test when key is symbol.
62 JSHandle<JSTaggedValue> symbolName(factory->NewFromStdString("s"));
63 JSHandle<JSSymbol> privateNameSymbol = factory->NewPrivateNameSymbol(symbolName);
64 JSHandle<JSTaggedValue> symbolValue = JSHandle<JSTaggedValue>::Cast(privateNameSymbol);
65 JSHandle<JSTaggedValue> metaData2(thread, JSTaggedValue(2)); // test metaData : 2
66 hash = TransitionsDictionary::Hash(symbolValue.GetTaggedValue(), metaData2.GetTaggedValue());
67 EXPECT_EQ(hash, 117); // 117 : 115 + 2
68 }
69
HWTEST_F_L0(TransitionsDictionaryTest,GetKeyIndex)70 HWTEST_F_L0(TransitionsDictionaryTest, GetKeyIndex)
71 {
72 int entry = 10;
73 EXPECT_EQ(TransitionsDictionary::GetKeyIndex(entry), 33); // 33 : 3 + 10 * 3 + 0
74 }
75
HWTEST_F_L0(TransitionsDictionaryTest,GetValueIndex)76 HWTEST_F_L0(TransitionsDictionaryTest, GetValueIndex)
77 {
78 int entry = 10;
79 EXPECT_EQ(TransitionsDictionary::GetValueIndex(entry), 34); // 34 : 3 + 10 * 3 + 1
80 }
81
HWTEST_F_L0(TransitionsDictionaryTest,GetEntryIndex)82 HWTEST_F_L0(TransitionsDictionaryTest, GetEntryIndex)
83 {
84 int entry = 10;
85 EXPECT_EQ(TransitionsDictionary::GetEntryIndex(entry), 33); // 33 : 3 + 10 * 3
86 }
87
HWTEST_F_L0(TransitionsDictionaryTest,Create)88 HWTEST_F_L0(TransitionsDictionaryTest, Create)
89 {
90 int numberOfElements = 8;
91 JSHandle<TransitionsDictionary> transDic = TransitionsDictionary::Create(thread, numberOfElements);
92 EXPECT_EQ(transDic->GetLength(), 27U); // 27 : 3 + 8 * 3
93 EXPECT_EQ(transDic->EntriesCount(), 0);
94 EXPECT_EQ(transDic->HoleEntriesCount(), 0);
95 }
96
HWTEST_F_L0(TransitionsDictionaryTest,Shrink)97 HWTEST_F_L0(TransitionsDictionaryTest, Shrink)
98 {
99 auto vm = thread->GetEcmaVM();
100 auto factory = vm->GetFactory();
101 int numberOfElements = 64;
102 JSHandle<TransitionsDictionary> transDic = TransitionsDictionary::Create(thread, numberOfElements);
103 EXPECT_EQ(transDic->GetLength(), 195U); // 195 : 3 + 64 * 3
104 EXPECT_EQ(transDic->EntriesCount(), 0);
105
106 JSHandle<JSTaggedValue> metaData(thread, JSTaggedValue::Undefined());
107 int eleNum = 7;
108 for (int index = 0; index < eleNum; index++) {
109 std::string keyStr = "key" + std::to_string(index);
110 JSHandle<JSTaggedValue> key(factory->NewFromStdString(keyStr));
111 JSHandle<JSTaggedValue> value(factory->NewEcmaHClass(JSObject::SIZE, JSType::JS_OBJECT));
112 TransitionsDictionary::PutIfAbsent(thread, transDic, key, value, metaData);
113 }
114 JSHandle<TransitionsDictionary> transDicAfterShink = TransitionsDictionary::Shrink(thread, transDic);
115 EXPECT_EQ(transDicAfterShink->GetLength(), 51U); // (1 << (32 - Clz((7 + (7 >> 1)) - 1))) * 3 + 3
116 EXPECT_EQ(transDic->EntriesCount(), eleNum);
117 }
118
HWTEST_F_L0(TransitionsDictionaryTest,Get_Set_Attributes)119 HWTEST_F_L0(TransitionsDictionaryTest, Get_Set_Attributes)
120 {
121 int numberOfElements = 8;
122 JSHandle<TransitionsDictionary> transDic = TransitionsDictionary::Create(thread, numberOfElements);
123 uint32_t length = transDic->GetLength();
124 EXPECT_EQ(length, 27U); // 27 : 3 + 8 * 3
125
126 for (int index = 0; index < numberOfElements; index++) {
127 transDic->SetAttributes(thread, index, JSTaggedValue(index));
128 JSTaggedValue value = transDic->GetAttributes(index);
129 EXPECT_EQ(value, JSTaggedValue(index));
130 }
131 }
132
133 using TestCommonCB = std::function<void(JSThread *, int index,
134 JSHandle<JSTaggedValue> &, JSHandle<JSTaggedValue> &)>;
TestCommon(JSThread * thread,int numberOfElements,TestCommonCB cb)135 void TestCommon(JSThread *thread, int numberOfElements, TestCommonCB cb)
136 {
137 auto factory = thread->GetEcmaVM()->GetFactory();
138
139 for (int index = 0; index < numberOfElements; index++) {
140 std::string keyStr = "key" + std::to_string(index);
141 JSHandle<JSTaggedValue> key(factory->NewFromStdString(keyStr));
142 JSHandle<JSTaggedValue> value(factory->NewEcmaHClass(JSObject::SIZE, JSType::JS_OBJECT));
143 cb(thread, index, key, value);
144 }
145 }
146
HWTEST_F_L0(TransitionsDictionaryTest,SetEntry)147 HWTEST_F_L0(TransitionsDictionaryTest, SetEntry)
148 {
149 int numberOfElements = 8;
150 JSHandle<TransitionsDictionary> transDic = TransitionsDictionary::Create(thread, numberOfElements);
151
152 JSHandle<JSTaggedValue> metaData(thread, JSTaggedValue::Undefined());
153 TestCommon(thread, numberOfElements,
154 [&](JSThread *thread, int index, JSHandle<JSTaggedValue> &key, JSHandle<JSTaggedValue> &value) {
155 transDic->SetEntry(thread, index, key.GetTaggedValue(), value.GetTaggedValue(),
156 metaData.GetTaggedValue());
157 EXPECT_EQ(transDic->GetKey(index), key.GetTaggedValue());
158 });
159 }
160
HWTEST_F_L0(TransitionsDictionaryTest,FindEntry)161 HWTEST_F_L0(TransitionsDictionaryTest, FindEntry)
162 {
163 int numberOfElements = 8;
164 JSHandle<TransitionsDictionary> transDic = TransitionsDictionary::Create(thread, numberOfElements);
165
166 JSHandle<JSTaggedValue> metaData(thread, JSTaggedValue::Undefined());
167 TestCommon(thread, numberOfElements,
168 [&](JSThread *thread, int index, JSHandle<JSTaggedValue> &key, JSHandle<JSTaggedValue> &value) {
169 transDic = TransitionsDictionary::PutIfAbsent(thread, transDic, key, value, metaData);
170 int foundEntry = transDic->FindEntry(key.GetTaggedValue(), metaData.GetTaggedValue());
171 EXPECT_EQ(index + 3, foundEntry); // 3 : table header size
172 });
173 }
174
HWTEST_F_L0(TransitionsDictionaryTest,RemoveElement)175 HWTEST_F_L0(TransitionsDictionaryTest, RemoveElement)
176 {
177 int numberOfElements = 8;
178 JSHandle<TransitionsDictionary> transDic = TransitionsDictionary::Create(thread, numberOfElements);
179 JSHandle<JSTaggedValue> metaData(thread, JSTaggedValue::Undefined());
180 TestCommon(thread, numberOfElements,
181 [&](JSThread *thread, int index, JSHandle<JSTaggedValue> &key, JSHandle<JSTaggedValue> &value) {
182 transDic = TransitionsDictionary::PutIfAbsent(thread, transDic, key, value, metaData);
183 });
184 auto factory = thread->GetEcmaVM()->GetFactory();
185 JSHandle<JSTaggedValue> key7(factory->NewFromStdString("key7")); // test remove element by "key7"
186 int foundEntry = transDic->FindEntry(key7.GetTaggedValue(), metaData.GetTaggedValue());
187 EXPECT_EQ(foundEntry, 7 + 3);
188 EXPECT_EQ(transDic->EntriesCount(), 8);
189
190 transDic->RemoveElement(thread, foundEntry);
191 foundEntry = transDic->FindEntry(key7.GetTaggedValue(), metaData.GetTaggedValue());
192 EXPECT_EQ(foundEntry, -1); // -1 : not found entry
193 EXPECT_EQ(transDic->EntriesCount(), 7);
194 }
195
HWTEST_F_L0(TransitionsDictionaryTest,PutIfAbsent)196 HWTEST_F_L0(TransitionsDictionaryTest, PutIfAbsent)
197 {
198 auto vm = thread->GetEcmaVM();
199 auto factory = vm->GetFactory();
200 int numberOfElements = 8;
201 JSHandle<TransitionsDictionary> transDic = TransitionsDictionary::Create(thread, numberOfElements);
202 JSHandle<JSTaggedValue> metaData(thread, JSTaggedValue::Undefined());
203 vm->SetEnableForceGC(false);
204 for (int index = 0; index < numberOfElements; index++) {
205 std::string keyStr = "key" + std::to_string(index);
206 JSHandle<JSTaggedValue> key(factory->NewFromStdString(keyStr));
207 JSHandle<JSTaggedValue> value(factory->NewEcmaHClass(JSObject::SIZE, JSType::JS_OBJECT));
208 transDic = TransitionsDictionary::PutIfAbsent(thread, transDic, key, value, metaData);
209 int foundEntry = transDic->FindEntry(key.GetTaggedValue(), metaData.GetTaggedValue());
210 EXPECT_EQ(foundEntry, index + 3);
211
212 JSTaggedValue foundValue = transDic->GetValue(foundEntry);
213 JSTaggedValue weakValue = value->CreateAndGetWeakRef();
214 EXPECT_EQ(foundValue, weakValue);
215 }
216 vm->SetEnableForceGC(true);
217 }
218
HWTEST_F_L0(TransitionsDictionaryTest,Remove)219 HWTEST_F_L0(TransitionsDictionaryTest, Remove)
220 {
221 int numberOfElements = 64;
222 int eleNum = 7;
223 JSHandle<TransitionsDictionary> transDic = TransitionsDictionary::Create(thread, numberOfElements);
224 JSHandle<JSTaggedValue> metaData(thread, JSTaggedValue::Undefined());
225 TestCommon(thread, eleNum,
226 [&](JSThread *thread, int index, JSHandle<JSTaggedValue> &key, JSHandle<JSTaggedValue> &value) {
227 transDic = TransitionsDictionary::PutIfAbsent(thread, transDic, key, value, metaData);
228 });
229 auto factory = thread->GetEcmaVM()->GetFactory();
230 JSHandle<JSTaggedValue> key6(factory->NewFromStdString("key6")); // test remove element by "key6"
231 EXPECT_EQ(transDic->EntriesCount(), 7);
232 EXPECT_EQ(transDic->GetLength(), 195U); // 195 : 3 + 64 * 3
233
234 transDic = TransitionsDictionary::Remove(thread, transDic, key6, metaData.GetTaggedValue());
235 EXPECT_EQ(transDic->EntriesCount(), 6); // 6 : 7 - 1
236 EXPECT_EQ(transDic->GetLength(), 51U); // (1 << (32 - Clz((6 + (6 >> 1)) - 1))) * 3 + 3
237 }
238
HWTEST_F_L0(TransitionsDictionaryTest,Rehash)239 HWTEST_F_L0(TransitionsDictionaryTest, Rehash)
240 {
241 int numberOfElements = 64;
242 int eleNum = 7;
243 JSHandle<TransitionsDictionary> transDic = TransitionsDictionary::Create(thread, numberOfElements);
244 JSHandle<JSTaggedValue> metaData(thread, JSTaggedValue::Undefined());
245 TestCommon(thread, eleNum,
246 [&](JSThread *thread, int index, JSHandle<JSTaggedValue> &key, JSHandle<JSTaggedValue> &value) {
247 transDic = TransitionsDictionary::PutIfAbsent(thread, transDic, key, value, metaData);
248 });
249 EXPECT_EQ(transDic->HoleEntriesCount(), 0);
250
251 int lastEntry = 7 + 3;
252 transDic->RemoveElement(thread, lastEntry); // remove one element
253 EXPECT_EQ(transDic->HoleEntriesCount(), 1);
254
255 transDic->Rehash(thread, *transDic);
256 EXPECT_EQ(transDic->HoleEntriesCount(), 0);
257 }
258 } // namespace panda::test