1/*
2 * Copyright (c) 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/base/sort_helper.h"
17#include "ecmascript/base/array_helper.h"
18#include "ecmascript/tagged_array-inl.h"
19
20namespace panda::ecmascript::base {
21void TimSort::Sort(JSThread *thread, JSHandle<TaggedArray> &elements, const JSHandle<JSTaggedValue> &fn)
22{
23    uint32_t low = 0;
24    uint32_t len = elements->GetLength();
25    uint32_t nRemaining = len;
26    if (nRemaining < 2) { // 2: means sorted.
27        return;
28    }
29    if (nRemaining < MIN_MERGE) {
30        int initRunLen = CountRunAndMakeAscending(thread, elements, low, len, fn);
31        BinarySort(thread, elements, low, len, low + initRunLen, fn);
32        return;
33    }
34
35    TimSort ts(thread, elements, fn);
36    uint32_t minRunLength = static_cast<uint32_t>(ComputeMinRunLength(len));
37
38    while (nRemaining != 0) {
39        uint32_t runLen = static_cast<uint32_t>(CountRunAndMakeAscending(thread, elements, low, len, fn));
40        if (runLen < minRunLength) {
41            uint32_t force = std::min(nRemaining, minRunLength);
42            BinarySort(thread, elements, low, low + force, low + runLen, fn);
43            runLen = force;
44        }
45
46        ts.PushRun(low, runLen);
47        ts.MergeCollapse();
48        low += runLen;
49        nRemaining -= runLen;
50    }
51    ASSERT(low = len);
52    ts.MergeForceCollapse();
53    ASSERT(ts.pending_.size() == 1);
54}
55
56int TimSort::CountRunAndMakeAscending(JSThread *thread, JSHandle<TaggedArray> &array,
57                                      int lo, int hi, const JSHandle<JSTaggedValue> &fn)
58{
59    ASSERT(lo < hi);
60    int runHi = lo + 1;
61    if (runHi == hi) {
62        return 1;
63    }
64    int runLength = 2;
65    JSMutableHandle<JSTaggedValue> runHiValue(thread, array->Get(runHi));
66    JSMutableHandle<JSTaggedValue> previousValue(thread, array->Get(runHi - 1));
67    double order = ArrayHelper::SortCompare(thread, fn, runHiValue, previousValue);
68    bool isDescending = order < 0 ? true : false;
69    previousValue.Update(runHiValue.GetTaggedValue());
70    for (int i = runHi + 1; i < hi; i++) {
71        runHiValue.Update(array->Get(i));
72        order = ArrayHelper::SortCompare(thread, fn, runHiValue, previousValue);
73        if (isDescending) {
74            if (order >= 0) break;
75        } else {
76            if (order < 0) break;
77        }
78        previousValue.Update(runHiValue.GetTaggedValue());
79        ++runLength;
80    }
81    if (isDescending) {
82        ReverseRange(thread, array, lo, lo + runLength);
83    }
84    return runLength;
85}
86
87void TimSort::ReverseRange(JSThread *thread, JSHandle<TaggedArray> &array, int from, int to)
88{
89    int low = from;
90    int high = to - 1;
91    JSMutableHandle<JSTaggedValue> elementLow(thread, JSTaggedValue::Undefined());
92    JSMutableHandle<JSTaggedValue> elementHigh(thread, JSTaggedValue::Undefined());
93    while (low < high) {
94        elementLow.Update(array->Get(low));
95        elementHigh.Update(array->Get(high));
96        array->Set(thread, low++, elementHigh);
97        array->Set(thread, high--, elementLow);
98    }
99}
100
101void TimSort::BinarySort(JSThread *thread, JSHandle<TaggedArray> &array,
102                         int lo, int hi, int start, JSHandle<JSTaggedValue> fn)
103{
104    ASSERT(lo <= start && start <= hi);
105    if (start == lo) {
106        start++;
107    }
108    JSMutableHandle<JSTaggedValue> midVal(thread, JSTaggedValue::Undefined());
109    JSMutableHandle<JSTaggedValue> tmpVal(thread, JSTaggedValue::Undefined());
110    JSMutableHandle<JSTaggedValue> pivotVal(thread, JSTaggedValue::Undefined());
111    for (; start < hi; start++) {
112        int left = lo;
113        int right = start;
114        pivotVal.Update(array->Get(right));
115        ASSERT(left <= right);
116        while (left < right) {
117            int mid = (left + right) >> 1;
118            midVal.Update(array->Get(mid));
119            if (ArrayHelper::SortCompare(thread, fn, pivotVal, midVal) < 0) {
120                right = mid;
121            } else {
122                left = mid + 1;
123            }
124        }
125        ASSERT(left == right);
126
127        for (int p = start; p > left; --p) {
128            tmpVal.Update(array->Get(p - 1));
129            array->Set(thread, p, tmpVal);
130        }
131        array->Set(thread, left, pivotVal);
132    }
133}
134
135void TimSort::MergeCollapse()
136{
137    while (pending_.size() > 1) {
138        int n = static_cast<int>(pending_.size() - 2);
139        if ((n > 0 && pending_[n - 1].len <= pending_[n].len + pending_[n + 1].len) ||
140            (n > 1 && pending_[n - 2].len <= pending_[n - 1].len + pending_[n].len)) { //2: means minus 2
141            if (pending_[n - 1].len < pending_[n + 1].len) {
142                --n;
143            }
144            MergeAt(n);
145        } else if (pending_[n].len <= pending_[n + 1].len) {
146            MergeAt(n);
147        } else {
148            break;
149        }
150    }
151}
152
153void TimSort::MergeForceCollapse()
154{
155    while (pending_.size() > 1) {
156        int n = static_cast<int>(pending_.size() - 2);
157        if (n > 0 && pending_[n - 1].len < pending_[n + 1].len) {
158            --n;
159        }
160        MergeAt(n);
161    }
162}
163
164void TimSort::MergeAt(int i)
165{
166    const int stackSize = static_cast<int>(pending_.size());
167    ASSERT(stackSize >= 2); // 2: stackSize
168    ASSERT(i >= 0);
169    ASSERT(i == stackSize - 2 || i == stackSize - 3);  // the 2nd-last and 3rd-last run.
170
171    int base1 = pending_[i].base;
172    int len1 = pending_[i].len;
173    int base2 = pending_[i + 1].base;
174    int len2 = pending_[i + 1].len;
175
176    ASSERT(len1 > 0 && len2 > 0);
177    ASSERT(base1 + len1 == base2);
178
179    pending_[i].len = len1 + len2;
180    if (i == stackSize - 3) { // 3: 3rd-last run
181        pending_[i + 1] = pending_[i + 2]; // 2: means plus 2
182    }
183    pending_.pop_back();
184
185    JSHandle<JSTaggedValue> key1(thread_, elements_->Get(base2));
186    int k = GallopRight(elements_, key1, base1, len1, 0);
187    ASSERT(k >= 0);
188    base1 += k;
189    len1 -= k;
190    if (len1 == 0) {
191        return;
192    }
193    JSHandle<JSTaggedValue> key2(thread_, elements_->Get(base1 + len1 - 1));
194    len2 = GallopLeft(elements_, key2, base2, len2, len2 - 1);
195    ASSERT(len2 >= 0);
196    if (len2 == 0) {
197        return;
198    }
199    // Merge remaining runs, using tmp array with min(len1, len2) elements_
200    if (len1 <= len2) {
201        MergeLo(base1, len1, base2, len2);
202    } else {
203        MergeHi(base1, len1, base2, len2);
204    }
205}
206
207int TimSort::GallopLeft(JSHandle<TaggedArray> &array,
208                        JSHandle<JSTaggedValue> key, int base, int len, int hint)
209{
210    ASSERT(len > 0 && hint >= 0 && hint < len);
211    int lastOfs = 0;
212    int ofs = 1;
213    JSHandle<JSTaggedValue> baseHintElement(thread_, array->Get(base + hint));
214    JSMutableHandle<JSTaggedValue> offsetElement(thread_, JSTaggedValue::Undefined());
215    JSMutableHandle<JSTaggedValue> mElement(thread_, JSTaggedValue::Undefined());
216    double order = ArrayHelper::SortCompare(thread_, fn_, key, baseHintElement);
217    if (order > 0) {
218        int maxOfs = len - hint;
219        while (ofs < maxOfs) {
220            offsetElement.Update(array->Get(base + hint + ofs));
221            order = ArrayHelper::SortCompare(thread_, fn_, key, offsetElement);
222            if (order <= 0) break;
223
224            lastOfs = ofs;
225            ofs = (ofs << 1) + 1;
226            if (ofs <= 0) {
227                ofs = maxOfs;
228            }
229        }
230        if (ofs > maxOfs) {
231            ofs = maxOfs;
232        }
233        lastOfs += hint;
234        ofs += hint;
235    } else {
236        int maxOfs = hint + 1;
237        while (ofs < maxOfs) {
238            offsetElement.Update(array->Get(base + hint - ofs));
239            order = ArrayHelper::SortCompare(thread_, fn_, key, offsetElement);
240            if (order > 0) break;
241
242            lastOfs = ofs;
243            ofs = (ofs << 1) + 1;
244            if (ofs <= 0) {
245                ofs = maxOfs;
246            }
247        }
248        if (ofs > maxOfs) {
249            ofs = maxOfs;
250        }
251        int tmp = lastOfs;
252        lastOfs = hint - ofs;
253        ofs = hint - tmp;
254    }
255    ASSERT(-1 <= lastOfs && lastOfs < ofs && ofs <= len);
256    lastOfs++;
257    while (lastOfs < ofs) {
258        int m = lastOfs + ((ofs - lastOfs) >> 1);
259        mElement.Update(array->Get(base + m));
260        if (ArrayHelper::SortCompare(thread_, fn_, key, mElement) > 0) {
261            lastOfs = m + 1;
262        } else {
263            ofs = m;
264        }
265    }
266    ASSERT(lastOfs == ofs);
267    return ofs;
268}
269
270int TimSort::GallopRight(JSHandle<TaggedArray> &array,
271                         JSHandle<JSTaggedValue> key, int base, int len, int hint)
272{
273    ASSERT(len > 0 && hint >= 0 && hint < len);
274    int lastOfs = 0;
275    int ofs = 1;
276    JSHandle<JSTaggedValue> baseHintElement(thread_, array->Get(base + hint));
277    JSMutableHandle<JSTaggedValue> offsetElement(thread_, JSTaggedValue::Undefined());
278    JSMutableHandle<JSTaggedValue> mElement(thread_, JSTaggedValue::Undefined());
279    double order = ArrayHelper::SortCompare(thread_, fn_, key, baseHintElement);
280    if (order < 0) {
281        int maxOfs = hint + 1;
282        while (ofs < maxOfs) {
283            offsetElement.Update(array->Get(base + hint - ofs));
284            order = ArrayHelper::SortCompare(thread_, fn_, key, offsetElement);
285            if (order >= 0) break;
286
287            lastOfs = ofs;
288            ofs = (ofs << 1) + 1;
289            if (ofs <= 0) {
290                ofs = maxOfs;
291            }
292        }
293        if (ofs > maxOfs) {
294            ofs = maxOfs;
295        }
296        int tmp = lastOfs;
297        lastOfs = hint - ofs;
298        ofs = hint - tmp;
299    } else {
300        int maxOfs = len - hint;
301        while (ofs < maxOfs) {
302            offsetElement.Update(array->Get(base + hint + ofs));
303            order = ArrayHelper::SortCompare(thread_, fn_, key, offsetElement);
304            if (order < 0) break;
305
306            lastOfs = ofs;
307            ofs = (ofs << 1) + 1;
308            if (ofs <= 0) {
309                ofs = maxOfs;
310            }
311        }
312        if (ofs > maxOfs) {
313            ofs = maxOfs;
314        }
315        lastOfs += hint;
316        ofs += hint;
317    }
318    ASSERT(-1 <= lastOfs && lastOfs < ofs && ofs <= len);
319    lastOfs++;
320    while (lastOfs < ofs) {
321        int m = lastOfs + ((ofs - lastOfs) >> 1);
322        mElement.Update(array->Get(base + m));
323        if (ArrayHelper::SortCompare(thread_, fn_, key, mElement) < 0) {
324            ofs = m;
325        } else {
326            lastOfs = m + 1;
327        }
328    }
329    return ofs;
330}
331
332void TimSort::MergeLo(int base1, int len1, int base2, int len2)
333{
334    ASSERT(len1 > 0 && len2 > 0 && base1 + len1 == base2);
335    JSHandle<TaggedArray> workArray = elements_;
336    JSHandle<TaggedArray> tmpArray = GetTempArray(len1);
337    this->CopyArray(workArray, base1, tmpArray, 0, len1);
338
339    JSMutableHandle<JSTaggedValue> tmpElement(thread_, JSTaggedValue::Undefined());
340    JSMutableHandle<JSTaggedValue> cmp1Element(thread_, JSTaggedValue::Undefined());
341    JSMutableHandle<JSTaggedValue> cmp2Element(thread_, JSTaggedValue::Undefined());
342
343    int cursor1 = 0;
344    int cursor2 = base2;
345    int dest = base1;
346    this->CopyArray(workArray, base1, tmpArray, cursor1, len1);
347
348    tmpElement.Update(workArray->Get(cursor2++));
349    workArray->Set(thread_, dest++, tmpElement);
350
351    if (--len2 == 0) {
352        this->CopyArray(tmpArray, cursor1, workArray, dest, len1);
353        return;
354    }
355    if (len1 == 1) {
356        this->CopyArray(workArray, cursor2, workArray, dest, len2);
357        tmpElement.Update(tmpArray->Get(cursor1));
358        workArray->Set(thread_, dest + len2, tmpElement);
359        return;
360    }
361    int minGallop = minGallop_;
362    while (true) {
363        int count1 = 0;
364        int count2 = 0;
365        do {
366            ASSERT(len1 > 1 && len2 > 0);
367            cmp1Element.Update(workArray->Get(cursor2));
368            cmp2Element.Update(tmpArray->Get(cursor1));
369
370            if (ArrayHelper::SortCompare(thread_, fn_, cmp1Element, cmp2Element) < 0) {
371                tmpElement.Update(workArray->Get(cursor2++));
372                workArray->Set(thread_, dest++, tmpElement);
373                count2++;
374                count1 = 0;
375                if (--len2 == 0) {
376                    goto epilogue;
377                }
378            } else {
379                tmpElement.Update(tmpArray->Get(cursor1++));
380                workArray->Set(thread_, dest++, tmpElement);
381                count1++;
382                count2 = 0;
383                if (--len1 == 1) {
384                    goto epilogue;
385                }
386            }
387        } while ((count1 | count2) < minGallop);
388
389        do {
390            ASSERT(len1 > 1 && len2 > 0);
391            JSHandle<JSTaggedValue> cursorVal(thread_, workArray->Get(cursor2));
392            count1 = GallopRight(tmpArray, cursorVal, cursor1, len1, 0);
393            if (count1 != 0) {
394                this->CopyArray(tmpArray, cursor1, workArray, dest, count1);
395                dest += count1;
396                cursor1 += count1;
397                len1 -= count1;
398                if (len1 <= 1) {
399                    goto epilogue;
400                }
401            }
402            tmpElement.Update(workArray->Get(cursor2++));
403            workArray->Set(thread_, dest++, tmpElement);
404            if (--len2 == 0) {
405                goto epilogue;
406            }
407            JSHandle<JSTaggedValue> cursorVal2(thread_, tmpArray->Get(cursor1));
408            count2 = GallopLeft(workArray, cursorVal2, cursor2, len2, 0);
409            if (count2 != 0) {
410                this->CopyArray(workArray, cursor2, workArray, dest, count2);
411                dest += count2;
412                cursor2 += count2;
413                len2 -= count2;
414                if (len2 == 0) {
415                    goto epilogue;
416                }
417            }
418            tmpElement.Update(tmpArray->Get(cursor1++));
419            workArray->Set(thread_, dest++, tmpElement);
420            if (--len1 == 1) {
421                goto epilogue;
422            }
423            minGallop--;
424        } while ((count1 >= MIN_GALLOP) | (count2 >= MIN_GALLOP));
425
426        if (minGallop < 0) {
427            minGallop = 0;
428        }
429        minGallop += 2; // 2: means plus 2
430    }
431
432    epilogue: // merge what is left from either cursor1 or cursor2
433
434    minGallop_ = std::min(minGallop, 1);
435    if (len1 == 1) {
436        ASSERT(len2 > 0);
437        this->CopyArray(workArray, cursor2, workArray, dest, len2);
438        tmpElement.Update(tmpArray->Get(cursor1));
439        workArray->Set(thread_, dest + len2, tmpElement);
440    } else {
441        ASSERT(len1 != 0);
442        ASSERT(len2 == 0 && len1 > 1);
443        this->CopyArray(tmpArray, cursor1, workArray, dest, len1);
444    }
445}
446
447void TimSort::MergeHi(int base1, int len1, int base2, int len2)
448{
449    JSHandle<TaggedArray> workArray = elements_;
450    JSHandle<TaggedArray> tmpArray = GetTempArray(len2);
451
452    JSMutableHandle<JSTaggedValue> tmpElement(thread_, JSTaggedValue::Undefined());
453    JSMutableHandle<JSTaggedValue> cmp1Element(thread_, JSTaggedValue::Undefined());
454    JSMutableHandle<JSTaggedValue> cmp2Element(thread_, JSTaggedValue::Undefined());
455
456    this->CopyArray(workArray, base2, tmpArray, 0, len2);
457    int cursor1 = base1 + len1 - 1;
458    int cursor2 =  len2 - 1;
459    int dest = base2 + len2 - 1;
460
461    tmpElement.Update(workArray->Get(cursor1--));
462    workArray->Set(thread_, dest--, tmpElement);
463
464    if (--len1 == 0) {
465        this->CopyArray(tmpArray, 0, workArray, dest - (len2 - 1), len2);
466        return;
467    }
468    if (len2 == 1) {
469        dest -= len1;
470        cursor1 -= len1;
471        this->CopyArray(workArray, cursor1 + 1, workArray, dest + 1, len1);
472        tmpElement.Update(tmpArray->Get(cursor2));
473        workArray->Set(thread_, dest, tmpElement);
474        return;
475    }
476    int minGallop = minGallop_;
477    while (true) {
478        int count1 = 0;
479        int count2 = 0;
480        do {
481            ASSERT(len1 > 0 && len2 > 1);
482            cmp1Element.Update(workArray->Get(cursor1));
483            cmp2Element.Update(tmpArray->Get(cursor2));
484
485            if (ArrayHelper::SortCompare(thread_, fn_, cmp2Element, cmp1Element) < 0) {
486                tmpElement.Update(workArray->Get(cursor1--));
487                workArray->Set(thread_, dest--, tmpElement);
488                count1++;
489                count2 = 0;
490                if (--len1 == 0) {
491                    goto epilogue;
492                }
493            } else {
494                tmpElement.Update(tmpArray->Get(cursor2--));
495                workArray->Set(thread_, dest--, tmpElement);
496                count2++;
497                count1 = 0;
498                if (--len2 == 1) {
499                    goto epilogue;
500                }
501            }
502        } while ((count1 | count2) < minGallop);
503
504        do {
505            ASSERT(len1 > 0 && len2 > 1);
506            JSHandle<JSTaggedValue> cursorVal(thread_, tmpArray->Get(cursor2));
507            count1 = len1 - GallopRight(workArray, cursorVal, base1, len1, len1 - 1);
508            if (count1 != 0) {
509                dest -= count1;
510                cursor1 -= count1;
511                len1 -= count1;
512                this->CopyArray(workArray, cursor1 + 1, workArray, dest + 1, count1);
513                if (len1 == 0) {
514                    goto epilogue;
515                }
516            }
517            tmpElement.Update(tmpArray->Get(cursor2--));
518            workArray->Set(thread_, dest--, tmpElement);
519            if (--len2 == 1) {
520                goto epilogue;
521            }
522            JSHandle<JSTaggedValue> cursorVal2(thread_, workArray->Get(cursor1));
523            count2 = len2 - GallopLeft(tmpArray, cursorVal2, 0, len2, len2 - 1);
524            if (count2 != 0) {
525                dest -= count2;
526                cursor2 -= count2;
527                len2 -= count2;
528                this->CopyArray(tmpArray, cursor2 + 1, workArray, dest + 1, count2);
529                if (len2 <= 1) {
530                    goto epilogue;
531                }
532            }
533            tmpElement.Update(workArray->Get(cursor1--));
534            workArray->Set(thread_, dest--, tmpElement);
535            if (--len1 == 0) {
536                goto epilogue;
537            }
538            minGallop--;
539        } while ((count1 >= MIN_GALLOP) | (count2 >= MIN_GALLOP));
540
541        if (minGallop < 0) {
542            minGallop = 0;
543        }
544        minGallop += 2; // 2: means plus 2
545    }
546
547    epilogue: // merge what is left from either cursor1 or cursor2
548
549    minGallop_ = std::min(minGallop, 1);
550    if (len2 == 1) {
551        ASSERT(len1 > 0);
552        dest -= len1;
553        cursor1 -= len1;
554        this->CopyArray(workArray, cursor1 + 1, workArray, dest + 1, len1);
555        tmpElement.Update(tmpArray->Get(cursor2));
556        workArray->Set(thread_, dest, tmpElement);
557    } else {
558        ASSERT(len2 != 0);
559        ASSERT(len1 == 0 && len2 > 1);
560        this->CopyArray(tmpArray, 0, workArray, dest - (len2 - 1), len2);
561    }
562}
563
564void TimSort::CopyArray(JSHandle<TaggedArray> &src, int srcPos,
565                        JSHandle<TaggedArray> &dst, int dstPos, int length)
566{
567    DISALLOW_GARBAGE_COLLECTION;
568    ASSERT(srcPos >= 0);
569    ASSERT(dstPos >= 0);
570    ASSERT(static_cast<int64_t>(srcPos) <= static_cast<int64_t>(src->GetLength() - length));
571    ASSERT(static_cast<int64_t>(dstPos) <= static_cast<int64_t>(dst->GetLength() - length));
572
573    if (srcPos < dstPos) {
574        int srcIdx = srcPos + length - 1;
575        int dstIdx = dstPos + length - 1;
576        while (srcIdx >= srcPos) {
577            dst->Set(thread_, dstIdx--, src->Get(srcIdx--));
578        }
579    } else {
580        int srcIdx = srcPos;
581        int dstIdx = dstPos;
582        int to = srcPos + length;
583        while (srcIdx < to) {
584            dst->Set(thread_, dstIdx++, src->Get(srcIdx++));
585        }
586    }
587}
588}