1/*
2 * Copyright (c) 2022-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#include "ecmascript/js_api/js_api_lightweightset.h"
17
18#include "ecmascript/containers/containers_errors.h"
19#include "ecmascript/interpreter/interpreter.h"
20#include "ecmascript/js_array.h"
21#include "ecmascript/js_function.h"
22
23#include <codecvt>
24
25namespace panda::ecmascript {
26using ContainerError = containers::ContainerError;
27using ErrorFlag = containers::ErrorFlag;
28bool JSAPILightWeightSet::Add(JSThread *thread, const JSHandle<JSAPILightWeightSet> &obj,
29                              const JSHandle<JSTaggedValue> &value)
30{
31    CheckAndCopyValues(thread, obj);
32    uint32_t hashCode = obj->Hash(thread, value.GetTaggedValue());
33    JSHandle<TaggedArray> hashArray(thread, obj->GetHashes());
34    JSHandle<TaggedArray> valueArray(thread, obj->GetValues());
35    int32_t size = static_cast<int32_t>(obj->GetLength());
36    int32_t index = obj->GetHashIndex(thread, value, size);
37    if (index >= 0) {
38        return false;
39    }
40    index ^= JSAPILightWeightSet::HASH_REBELLION;
41    if (index < size) {
42        obj->AdjustArray(thread, hashArray, index, size, true);
43        obj->AdjustArray(thread, valueArray, index, size, true);
44    }
45    uint32_t capacity = hashArray->GetLength();
46    if (size + 1 >= static_cast<int32_t>(capacity)) {
47        // need expanding
48        uint32_t newCapacity = capacity << 1U;
49        hashArray = thread->GetEcmaVM()->GetFactory()->CopyArray(hashArray, capacity, newCapacity);
50        valueArray = thread->GetEcmaVM()->GetFactory()->CopyArray(valueArray, capacity, newCapacity);
51        obj->SetHashes(thread, hashArray);
52        obj->SetValues(thread, valueArray);
53    }
54    hashArray->Set(thread, index, JSTaggedValue(hashCode));
55    valueArray->Set(thread, index, value.GetTaggedValue());
56    size++;
57    obj->SetLength(size);
58    return true;
59}
60
61JSTaggedValue JSAPILightWeightSet::Get(const uint32_t index)
62{
63    TaggedArray *valueArray = TaggedArray::Cast(GetValues().GetTaggedObject());
64    return valueArray->Get(index);
65}
66
67JSHandle<TaggedArray> JSAPILightWeightSet::CreateSlot(const JSThread *thread, const uint32_t capacity)
68{
69    ASSERT_PRINT(capacity > 0, "size must be a non-negative integer");
70    ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
71    JSHandle<TaggedArray> taggedArray = factory->NewTaggedArray(capacity);
72    for (uint32_t i = 0; i < capacity; i++) {
73        taggedArray->Set(thread, i, JSTaggedValue::Hole());
74    }
75    return taggedArray;
76}
77
78int32_t JSAPILightWeightSet::GetHashIndex(const JSThread *thread, const JSHandle<JSTaggedValue> &value, int32_t size)
79{
80    uint32_t hashCode = Hash(thread, value.GetTaggedValue());
81    int32_t index = BinarySearchHashes(hashCode, size);
82    if (index < 0) {
83        return index;
84    }
85    TaggedArray *valueArray = TaggedArray::Cast(GetValues().GetTaggedObject());
86    if (index < size && (JSTaggedValue::SameValue(valueArray->Get(index), value.GetTaggedValue()))) {
87        return index;
88    }
89    TaggedArray *hashArray = TaggedArray::Cast(GetHashes().GetTaggedObject());
90    int32_t right = index;
91    while (right < size && (hashArray->Get(right).GetNumber() == hashCode)) {
92        if (JSTaggedValue::SameValue(valueArray->Get(right), value.GetTaggedValue())) {
93            return right;
94        }
95        right++;
96    }
97    int32_t left = index - 1;
98    while (left >= 0 && ((hashArray->Get(left).GetNumber() == hashCode))) {
99        if (JSTaggedValue::SameValue(valueArray->Get(left), value.GetTaggedValue())) {
100            return left;
101        }
102        left--;
103    }
104    return -right;
105}
106
107int32_t JSAPILightWeightSet::BinarySearchHashes(uint32_t hash, int32_t size)
108{
109    int32_t low = 0;
110    int32_t high = size - 1;
111    TaggedArray *hashArray = TaggedArray::Cast(GetHashes().GetTaggedObject());
112    while (low <= high) {
113        int32_t mid = (low + high) >> 1U;
114        uint32_t midVal = (uint32_t)(hashArray->Get(static_cast<uint32_t>(mid)).GetNumber());
115        if (midVal < hash) {
116            low = mid + 1;
117        } else {
118            if (midVal <= hash) {
119                return mid;
120            }
121            high = mid - 1;
122        }
123    }
124    return -(low + 1);
125}
126
127bool JSAPILightWeightSet::AddAll(JSThread *thread, const JSHandle<JSAPILightWeightSet> &obj,
128                                 const JSHandle<JSTaggedValue> &value)
129{
130    bool changed = false;
131    JSHandle<JSAPILightWeightSet> srcLightWeightSet = JSHandle<JSAPILightWeightSet>::Cast(value);
132    uint32_t srcSize = srcLightWeightSet->GetSize();
133    uint32_t size = obj->GetSize();
134    obj->EnsureCapacity(thread, obj, size + srcSize);
135    JSMutableHandle<JSTaggedValue> element(thread, JSTaggedValue::Undefined());
136    for (uint32_t i = 0; i < srcSize; i++) {
137        element.Update(srcLightWeightSet->GetValueAt(i));
138        changed |= JSAPILightWeightSet::Add(thread, obj, element);
139    }
140    return changed;
141}
142
143void JSAPILightWeightSet::EnsureCapacity(const JSThread *thread, const JSHandle<JSAPILightWeightSet> &obj,
144                                         uint32_t minimumCapacity)
145{
146    TaggedArray *hashes = TaggedArray::Cast(obj->GetValues().GetTaggedObject());
147    uint32_t capacity = hashes->GetLength();
148    uint32_t newCapacity = capacity;
149    if (capacity > minimumCapacity) {
150        return;
151    }
152    // adjust
153    while (newCapacity <= minimumCapacity) {
154        newCapacity = newCapacity << 1U;
155    }
156    obj->SizeCopy(thread, obj, capacity, newCapacity);
157}
158
159void JSAPILightWeightSet::SizeCopy(const JSThread *thread, const JSHandle<JSAPILightWeightSet> &obj,
160                                   uint32_t capacity, uint32_t newCapacity)
161{
162    JSHandle<TaggedArray> hashArray(thread, obj->GetHashes());
163    JSHandle<TaggedArray> valueArray(thread, obj->GetValues());
164    hashArray = thread->GetEcmaVM()->GetFactory()->CopyArray(hashArray, capacity, newCapacity);
165    valueArray = thread->GetEcmaVM()->GetFactory()->CopyArray(valueArray, capacity, newCapacity);
166
167    obj->SetValues(thread, hashArray);
168    obj->SetHashes(thread, valueArray);
169}
170
171bool JSAPILightWeightSet::IsEmpty()
172{
173    return GetLength() == 0;
174}
175
176JSTaggedValue JSAPILightWeightSet::GetValueAt(int32_t index)
177{
178    int32_t size = static_cast<int32_t>(GetLength());
179    if (index < 0 || index >= size) {
180        return JSTaggedValue::Undefined();
181    }
182    TaggedArray *values = TaggedArray::Cast(GetValues().GetTaggedObject());
183    return values->Get(index);
184}
185
186JSTaggedValue JSAPILightWeightSet::GetHashAt(int32_t index)
187{
188    int32_t size = static_cast<int32_t>(GetLength());
189    if (index < 0 || index >= size) {
190        return JSTaggedValue::Undefined();
191    }
192    TaggedArray *values = TaggedArray::Cast(GetHashes().GetTaggedObject());
193    return values->Get(index);
194}
195
196bool JSAPILightWeightSet::HasAll(const JSHandle<JSTaggedValue> &value)
197{
198    bool result = false;
199    uint32_t relocate = 0;
200    JSAPILightWeightSet *lightweightSet = JSAPILightWeightSet::Cast(value.GetTaggedValue().GetTaggedObject());
201    uint32_t size = GetLength();
202    uint32_t destSize = lightweightSet->GetLength();
203    TaggedArray *hashes = TaggedArray::Cast(GetHashes().GetTaggedObject());
204    TaggedArray *destHashes = TaggedArray::Cast(lightweightSet->GetHashes().GetTaggedObject());
205    if (destSize > size) {
206        return result;
207    }
208    for (uint32_t i = 0; i < destSize; i++) {
209        uint32_t destHashCode = destHashes->Get(i).GetNumber();
210        result = false;
211        for (uint32_t j = relocate; j < size; j++) {
212            uint32_t hashCode = hashes->Get(j).GetNumber();
213            if (destHashCode == hashCode) {
214                result = true;
215                relocate = j + 1;
216                break;
217            }
218        }
219        if (!result) {
220            break;
221        }
222    }
223    return result;
224}
225
226bool JSAPILightWeightSet::Has(const JSThread *thread, const JSHandle<JSTaggedValue> &value)
227{
228    uint32_t size = GetLength();
229    int32_t index = GetHashIndex(thread, value, size);
230    if (index < 0) {
231        return false;
232    }
233    return true;
234}
235
236bool JSAPILightWeightSet::HasHash(const JSHandle<JSTaggedValue> &hashCode)
237{
238    uint32_t size = GetLength();
239    int32_t index = BinarySearchHashes(hashCode.GetTaggedValue().GetNumber(), size);
240    if (index < 0) {
241        return false;
242    }
243    return true;
244}
245
246bool JSAPILightWeightSet::Equal(JSThread *thread, const JSHandle<JSAPILightWeightSet> &obj,
247                                const JSHandle<JSTaggedValue> &value)
248{
249    bool result = false;
250    JSHandle<TaggedArray> destHashes(thread, obj->GetValues());
251    uint32_t destSize = obj->GetLength();
252    uint32_t srcSize = 0;
253    JSMutableHandle<TaggedArray> srcHashes(thread, obj->GetHashes());
254    if (value.GetTaggedValue().IsJSAPILightWeightSet()) {
255        JSAPILightWeightSet *srcLightWeightSet = JSAPILightWeightSet::Cast(value.GetTaggedValue().GetTaggedObject());
256        srcSize = srcLightWeightSet->GetLength();
257        if (srcSize == 0 || destSize == 0) {
258            return false;
259        }
260        srcHashes.Update(srcLightWeightSet->GetHashes());
261    }
262    if (value.GetTaggedValue().IsJSArray()) {
263        srcHashes.Update(JSArray::ToTaggedArray(thread, value));
264        srcSize = srcHashes->GetLength();
265        if (srcSize == 0 || destSize == 0) {
266            return false;
267        }
268    }
269    if (srcSize != destSize) {
270        return false;
271    }
272    for (uint32_t i = 0; i < destSize; i++) {
273        JSTaggedValue compareValue = destHashes->Get(i);
274        JSTaggedValue values = srcHashes->Get(i);
275        if (compareValue.IsNumber() && values.IsNumber()) {
276            result = JSTaggedValue::SameValueNumberic(compareValue, values);
277        }
278        if (compareValue.IsString() && values.IsString()) {
279            result =
280                JSTaggedValue::StringCompare(EcmaString::Cast(compareValue.GetTaggedObject()),
281                                             EcmaString::Cast(values.GetTaggedObject()));
282        }
283        if (!result) {
284            return result;
285        }
286    }
287    return result;
288}
289
290void JSAPILightWeightSet::IncreaseCapacityTo(JSThread *thread, const JSHandle<JSAPILightWeightSet> &obj,
291                                             int32_t minCapacity)
292{
293    uint32_t capacity = TaggedArray::Cast(obj->GetValues().GetTaggedObject())->GetLength();
294    int32_t intCapacity = static_cast<int32_t>(capacity);
295    if (minCapacity <= 0 || intCapacity >= minCapacity) {
296        std::ostringstream oss;
297        oss << "The value of \"minimumCapacity\" is out of range. It must be > " << intCapacity
298            << ". Received value is: " << minCapacity;
299        JSTaggedValue error = ContainerError::BusinessError(thread, ErrorFlag::RANGE_ERROR, oss.str().c_str());
300        THROW_NEW_ERROR_AND_RETURN(thread, error);
301    }
302    JSHandle<TaggedArray> hashArray(thread, obj->GetHashes());
303    JSHandle<TaggedArray> newElements =
304        thread->GetEcmaVM()->GetFactory()->NewAndCopyTaggedArray(hashArray,
305                                                                 static_cast<uint32_t>(minCapacity), capacity);
306    obj->SetHashes(thread, newElements);
307}
308
309JSHandle<JSTaggedValue> JSAPILightWeightSet::GetIteratorObj(JSThread *thread, const JSHandle<JSAPILightWeightSet> &obj,
310                                                            IterationKind kind)
311{
312    ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
313    JSHandle<JSTaggedValue> iter =
314        JSHandle<JSTaggedValue>::Cast(factory->NewJSAPILightWeightSetIterator(obj, kind));
315    return iter;
316}
317
318JSTaggedValue JSAPILightWeightSet::ForEach(JSThread *thread, const JSHandle<JSTaggedValue> &thisHandle,
319                                           const JSHandle<JSTaggedValue> &callbackFn,
320                                           const JSHandle<JSTaggedValue> &thisArg)
321{
322    JSHandle<JSAPILightWeightSet> lightweightset = JSHandle<JSAPILightWeightSet>::Cast(thisHandle);
323    CheckAndCopyValues(thread, lightweightset);
324    uint32_t length = lightweightset->GetSize();
325    JSHandle<JSTaggedValue> undefined = thread->GlobalConstants()->GetHandledUndefined();
326    for (uint32_t k = 0; k < length; k++) {
327        JSTaggedValue kValue = lightweightset->GetValueAt(k);
328        EcmaRuntimeCallInfo *info =
329            EcmaInterpreter::NewRuntimeCallInfo(thread, callbackFn, thisArg, undefined, 3); // 3:three args
330        RETURN_VALUE_IF_ABRUPT_COMPLETION(thread, JSTaggedValue::Exception());
331        info->SetCallArg(kValue, kValue, thisHandle.GetTaggedValue());
332        JSTaggedValue funcResult = JSFunction::Call(info);
333        RETURN_VALUE_IF_ABRUPT_COMPLETION(thread, funcResult);
334        if (lightweightset->GetSize() != length) {  // prevent length change
335            length = lightweightset->GetSize();
336        }
337    }
338    return JSTaggedValue::Undefined();
339}
340
341int32_t JSAPILightWeightSet::GetIndexOf(const JSThread *thread, JSHandle<JSTaggedValue> &value)
342{
343    uint32_t size = GetLength();
344    int32_t index = GetHashIndex(thread, value, size);
345    return index;
346}
347
348JSTaggedValue JSAPILightWeightSet::Remove(JSThread *thread, JSHandle<JSTaggedValue> &value)
349{
350    uint32_t size = GetLength();
351    TaggedArray *valueArray = TaggedArray::Cast(GetValues().GetTaggedObject());
352    int32_t index = GetHashIndex(thread, value, size);
353    if (index < 0) {
354        return JSTaggedValue::Undefined();
355    }
356    JSTaggedValue result = valueArray->Get(index);
357    RemoveAt(thread, index);
358    return result;
359}
360
361bool JSAPILightWeightSet::RemoveAt(JSThread *thread, int32_t index)
362{
363    uint32_t size = GetLength();
364    if (index < 0 || index >= static_cast<int32_t>(size)) {
365        return false;
366    }
367    JSHandle<TaggedArray> valueArray(thread, GetValues());
368    JSHandle<TaggedArray> hashArray(thread, GetHashes());
369    RemoveValue(thread, hashArray, static_cast<uint32_t>(index), true);
370    RemoveValue(thread, valueArray, static_cast<uint32_t>(index));
371    SetLength(size - 1);
372    return true;
373}
374
375void JSAPILightWeightSet::RemoveValue(const JSThread *thread, JSHandle<TaggedArray> &taggedArray,
376                                      uint32_t index, bool isHash)
377{
378    uint32_t len = GetLength();
379    ASSERT(index < len);
380    TaggedArray::RemoveElementByIndex(thread, taggedArray, index, len, isHash);
381}
382
383void JSAPILightWeightSet::AdjustArray(JSThread *thread, JSHandle<TaggedArray> srcArray, uint32_t fromIndex,
384                                      uint32_t toIndex, bool direction)
385{
386    uint32_t size = GetLength();
387    uint32_t idx = size - 1;
388    if (direction) {
389        while (fromIndex < toIndex) {
390            JSTaggedValue value = srcArray->Get(idx);
391            srcArray->Set(thread, idx + 1, value);
392            idx--;
393            fromIndex++;
394        }
395    } else {
396        uint32_t moveSize = size - fromIndex;
397        for (uint32_t i = 0; i < moveSize; i++) {
398            if ((fromIndex + i) < size) {
399                JSTaggedValue value = srcArray->Get(fromIndex + i);
400                srcArray->Set(thread, toIndex + i, value);
401            } else {
402                srcArray->Set(thread, toIndex + i, JSTaggedValue::Hole());
403            }
404        }
405    }
406}
407
408JSTaggedValue JSAPILightWeightSet::ToString(JSThread *thread, const JSHandle<JSAPILightWeightSet> &obj)
409{
410    ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
411    std::u16string sepStr = std::wstring_convert<std::codecvt_utf8_utf16<char16_t>, char16_t> {}.from_bytes(",");
412
413    uint32_t length = obj->GetSize();
414    JSHandle<TaggedArray> valueArray(thread, obj->GetValues());
415    std::u16string concatStr;
416    JSMutableHandle<JSTaggedValue> values(thread, JSTaggedValue::Undefined());
417    for (uint32_t k = 0; k < length; k++) {
418        std::u16string nextStr;
419        values.Update(valueArray->Get(k));
420        if (!values->IsUndefined() && !values->IsNull()) {
421            JSHandle<EcmaString> nextStringHandle = JSTaggedValue::ToString(thread, values);
422            RETURN_EXCEPTION_IF_ABRUPT_COMPLETION(thread);
423            nextStr = EcmaStringAccessor(nextStringHandle).ToU16String();
424        }
425        if (k > 0) {
426            concatStr.append(sepStr);
427            concatStr.append(nextStr);
428            continue;
429        }
430        concatStr.append(nextStr);
431    }
432    char16_t *char16tData = concatStr.data();
433    auto *uint16tData = reinterpret_cast<uint16_t *>(char16tData);
434    uint32_t u16strSize = concatStr.size();
435    return factory->NewFromUtf16Literal(uint16tData, u16strSize).GetTaggedValue();
436}
437
438void JSAPILightWeightSet::Clear(JSThread *thread)
439{
440    TaggedArray *hashArray = TaggedArray::Cast(GetHashes().GetTaggedObject());
441    TaggedArray *valueArray = TaggedArray::Cast(GetValues().GetTaggedObject());
442    uint32_t size = GetLength();
443    for (uint32_t index = 0; index < size; index++) {
444        hashArray->Set(thread, index, JSTaggedValue::Hole());
445        valueArray->Set(thread, index, JSTaggedValue::Hole());
446    }
447    SetLength(0);
448}
449
450uint32_t JSAPILightWeightSet::Hash(const JSThread *thread, JSTaggedValue key)
451{
452    if (key.IsDouble() && key.GetDouble() == 0.0) {
453        key = JSTaggedValue(0);
454    }
455    if (key.IsSymbol()) {
456        auto symbolString = JSSymbol::Cast(key.GetTaggedObject());
457        return symbolString->GetHashField();
458    }
459    if (key.IsString()) {
460        auto keyString = EcmaString::Cast(key.GetTaggedObject());
461        return EcmaStringAccessor(keyString).GetHashcode();
462    }
463    if (key.IsECMAObject()) {
464        uint32_t hash = static_cast<uint32_t>(ECMAObject::Cast(key.GetTaggedObject())->GetHash());
465        if (hash == 0) {
466            hash = static_cast<uint32_t>(base::RandomGenerator::GenerateIdentityHash());
467            JSHandle<ECMAObject> ecmaObj(thread, key);
468            ECMAObject::SetHash(thread, hash, ecmaObj);
469        }
470        return hash;
471    }
472    if (key.IsInt()) {
473        uint32_t hash = static_cast<uint32_t>(key.GetInt());
474        return hash;
475    }
476    uint64_t keyValue = key.GetRawData();
477    return GetHash32(reinterpret_cast<uint8_t *>(&keyValue), sizeof(keyValue) / sizeof(uint8_t));
478}
479
480void JSAPILightWeightSet::CheckAndCopyValues(const JSThread *thread, JSHandle<JSAPILightWeightSet> obj)
481{
482    JSHandle<TaggedArray> values(thread, obj->GetValues());
483    // Check whether array is shared in the nonmovable space before set properties and elements.
484    // If true, then really copy array in the semi space.
485    ObjectFactory *factory = thread->GetEcmaVM()->GetFactory();
486    if (values.GetTaggedValue().IsCOWArray()) {
487        auto newArray = factory->CopyArray(values, values->GetLength(), values->GetLength(),
488            JSTaggedValue::Hole(), MemSpaceType::SEMI_SPACE);
489        obj->SetValues(thread, newArray.GetTaggedValue());
490    }
491}
492} // namespace panda::ecmascript
493