1/**
2 * Copyright (c) 2021-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 "file_item_container.h"
17#include "macros.h"
18#include "file_format_version.h"
19#include "pgo.h"
20
21namespace panda::panda_file {
22
23class ItemDeduper {
24public:
25    template <class T>
26    T *Deduplicate(T *item)
27    {
28        static_assert(std::is_base_of_v<BaseItem, T>);
29
30        ItemData item_data(item);
31        auto it = items_.find(item_data);
32        if (it == items_.cend()) {
33            items_.insert(item_data);
34            return item;
35        }
36
37        auto result = static_cast<T *>(it->GetItem());
38        if (item != result) {
39            item->SetNeedsEmit(false);
40        }
41
42        return result;
43    }
44
45    size_t GetUniqueCount() const
46    {
47        return items_.size();
48    }
49
50private:
51    class ItemWriter : public Writer {
52    public:
53        ItemWriter(std::vector<uint8_t> *buf, size_t offset) : buf_(buf), offset_(offset) {}
54        ~ItemWriter() override = default;
55
56        NO_COPY_SEMANTIC(ItemWriter);
57        NO_MOVE_SEMANTIC(ItemWriter);
58
59        bool WriteByte(uint8_t byte) override
60        {
61            buf_->push_back(byte);
62            ++offset_;
63            return true;
64        }
65
66        bool WriteBytes(const std::vector<uint8_t> &bytes) override
67        {
68            buf_->insert(buf_->end(), bytes.cbegin(), bytes.cend());
69            offset_ += bytes.size();
70            return true;
71        }
72
73        size_t GetOffset() const override
74        {
75            return offset_;
76        }
77
78    private:
79        std::vector<uint8_t> *buf_;
80        size_t offset_;
81    };
82
83    class ItemData {
84    public:
85        explicit ItemData(BaseItem *item) : item_(item)
86        {
87            Initialize();
88        }
89
90        ~ItemData() = default;
91
92        DEFAULT_COPY_SEMANTIC(ItemData);
93        NO_MOVE_SEMANTIC(ItemData);
94
95        BaseItem *GetItem() const
96        {
97            return item_;
98        }
99
100        uint32_t GetHash() const
101        {
102            ASSERT(IsInitialized());
103            return hash_;
104        }
105
106        bool operator==(const ItemData &item_data) const noexcept
107        {
108            ASSERT(IsInitialized());
109            return data_ == item_data.data_;
110        }
111
112    private:
113        bool IsInitialized() const
114        {
115            return !data_.empty();
116        }
117
118        void Initialize()
119        {
120            ASSERT(item_->NeedsEmit());
121
122            ItemWriter writer(&data_, item_->GetOffset());
123            [[maybe_unused]] auto res = item_->Write(&writer);
124            ASSERT(res);
125            ASSERT(data_.size() == item_->GetSize());
126
127            hash_ = GetHash32(data_.data(), data_.size());
128        }
129
130        BaseItem *item_;
131        uint32_t hash_ {0};
132        std::vector<uint8_t> data_;
133    };
134
135    struct ItemHash {
136        size_t operator()(const ItemData &item_data) const noexcept
137        {
138            return item_data.GetHash();
139        }
140    };
141
142    std::unordered_set<ItemData, ItemHash> items_;
143};
144
145template <class T, class C, class I, class P, class E, class... Args>
146static T *GetOrInsert(C &map, I &items, const P &pos, const E &key, bool is_foreign, Args &&... args)
147{
148    auto it = map.find(key);
149    if (it != map.cend()) {
150        auto *item = it->second;
151        if (item->IsForeign() == is_foreign) {
152            return static_cast<T *>(item);
153        }
154
155        UNREACHABLE();
156        return nullptr;
157    }
158
159    auto ii = items.insert(pos, std::make_unique<T>(std::forward<Args>(args)...));
160    auto *item = static_cast<T *>(ii->get());
161
162    [[maybe_unused]] auto res = map.insert({key, item});
163    ASSERT(res.second);
164    return item;
165}
166
167/*static*/
168uint8_t ItemContainer::apiVersion = 0;
169std::string ItemContainer::subApiVersion = DEFAULT_SUB_API_VERSION;
170
171ItemContainer::ItemContainer()
172{
173    items_end_ = items_.insert(items_.end(), std::make_unique<EndItem>());
174    code_items_end_ = items_.insert(items_.end(), std::make_unique<EndItem>());
175    debug_items_end_ = items_.insert(items_.end(), std::make_unique<EndItem>());
176    end_ = debug_items_end_->get();
177}
178
179ClassItem *ItemContainer::GetOrCreateClassItem(const std::string &str)
180{
181    return GetOrInsert<ClassItem>(class_map_, items_, items_end_, str, false, str, this);
182}
183
184ForeignClassItem *ItemContainer::GetOrCreateForeignClassItem(const std::string &str)
185{
186    return GetOrInsert<ForeignClassItem>(class_map_, foreign_items_, foreign_items_.end(), str, true, str, this);
187}
188
189StringItem *ItemContainer::GetOrCreateStringItem(const std::string &str)
190{
191    auto it = class_map_.find(str);
192    if (it != class_map_.cend()) {
193        return it->second->GetNameItem();
194    }
195
196    return GetOrInsert<StringItem>(string_map_, items_, items_end_, str, false, str, this);
197}
198
199LiteralArrayItem *ItemContainer::GetOrCreateLiteralArrayItem(const std::string &id)
200{
201    return GetOrInsert<LiteralArrayItem>(literalarray_map_, items_, items_end_, id, false, this);
202}
203
204ScalarValueItem *ItemContainer::GetOrCreateIntegerValueItem(uint32_t v)
205{
206    return GetOrInsert<ScalarValueItem>(int_value_map_, items_, items_end_, v, false, v, this);
207}
208
209ScalarValueItem *ItemContainer::GetOrCreateLongValueItem(uint64_t v)
210{
211    return GetOrInsert<ScalarValueItem>(long_value_map_, items_, items_end_, v, false, v, this);
212}
213
214ScalarValueItem *ItemContainer::GetOrCreateFloatValueItem(float v)
215{
216    return GetOrInsert<ScalarValueItem>(float_value_map_, items_, items_end_, bit_cast<uint32_t>(v), false, v, this);
217}
218
219ScalarValueItem *ItemContainer::GetOrCreateDoubleValueItem(double v)
220{
221    return GetOrInsert<ScalarValueItem>(double_value_map_, items_, items_end_, bit_cast<uint64_t>(v), false, v, this);
222}
223
224ScalarValueItem *ItemContainer::GetOrCreateIdValueItem(BaseItem *v)
225{
226    return GetOrInsert<ScalarValueItem>(id_value_map_, items_, items_end_, v, false, v, this);
227}
228
229ProtoItem *ItemContainer::GetOrCreateProtoItem(TypeItem *ret_type, const std::vector<MethodParamItem> &params)
230{
231    ProtoKey key(ret_type, params);
232    return GetOrInsert<ProtoItem>(proto_map_, items_, items_end_, key, false, ret_type, params, this);
233}
234
235PrimitiveTypeItem *ItemContainer::GetOrCreatePrimitiveTypeItem(Type type)
236{
237    return GetOrCreatePrimitiveTypeItem(type.GetId());
238}
239
240PrimitiveTypeItem *ItemContainer::GetOrCreatePrimitiveTypeItem(Type::TypeId type)
241{
242    return GetOrInsert<PrimitiveTypeItem>(primitive_type_map_, items_, items_end_, type, false, type, this);
243}
244
245LineNumberProgramItem *ItemContainer::CreateLineNumberProgramItem()
246{
247    auto it = items_.insert(debug_items_end_, std::make_unique<LineNumberProgramItem>(this));
248    auto *item = static_cast<LineNumberProgramItem *>(it->get());
249    [[maybe_unused]] auto res = line_number_program_index_item_.Add(item);
250    ASSERT(res);
251    return item;
252}
253
254void ItemContainer::DeduplicateLineNumberProgram(DebugInfoItem *item, ItemDeduper *deduper)
255{
256    auto *line_number_program = item->GetLineNumberProgram();
257    auto *deduplicated = deduper->Deduplicate(line_number_program);
258    if (deduplicated != line_number_program) {
259        item->SetLineNumberProgram(deduplicated);
260        line_number_program_index_item_.Remove(line_number_program);
261        line_number_program_index_item_.IncRefCount(deduplicated);
262    }
263}
264
265void ItemContainer::DeduplicateDebugInfo(MethodItem *method, ItemDeduper *debug_info_deduper,
266                                         ItemDeduper *line_number_program_deduper)
267{
268    auto *debug_item = method->GetDebugInfo();
269    if (debug_item == nullptr) {
270        return;
271    }
272
273    DeduplicateLineNumberProgram(debug_item, line_number_program_deduper);
274
275    auto *deduplicated = debug_info_deduper->Deduplicate(debug_item);
276    if (deduplicated != debug_item) {
277        method->SetDebugInfo(deduplicated);
278        line_number_program_index_item_.DecRefCount(debug_item->GetLineNumberProgram());
279    }
280}
281
282void ItemContainer::DeduplicateCodeAndDebugInfo()
283{
284    ItemDeduper line_number_program_deduper;
285    ItemDeduper debug_deduper;
286
287    for (auto &p : class_map_) {
288        auto *item = p.second;
289        if (item->IsForeign()) {
290            continue;
291        }
292
293        auto *class_item = static_cast<ClassItem *>(item);
294
295        class_item->VisitMethods(
296            [this, &debug_deduper, &line_number_program_deduper](BaseItem *param_item) {
297                auto *method_item = static_cast<MethodItem *>(param_item);
298                DeduplicateDebugInfo(method_item, &debug_deduper, &line_number_program_deduper);
299                return true;
300            });
301    }
302}
303
304static void DeduplicateAnnotationValue(AnnotationItem *annotation_item, ItemDeduper *deduper)
305{
306    auto *elems = annotation_item->GetElements();
307    const auto &tags = annotation_item->GetTags();
308
309    for (size_t i = 0; i < elems->size(); i++) {
310        auto tag = tags[i];
311
312        // try to dedupe only ArrayValueItems
313        switch (tag.GetItem()) {
314            case 'K':
315            case 'L':
316            case 'M':
317            case 'N':
318            case 'O':
319            case 'P':
320            case 'Q':
321            case 'R':
322            case 'S':
323            case 'T':
324            case 'U':
325            case 'V':
326            case 'W':
327            case 'X':
328            case 'Y':
329            case 'Z':
330            case '@':
331                break;
332            default:
333                continue;
334        }
335
336        auto &elem = (*elems)[i];
337        auto *value = elem.GetValue();
338        auto *deduplicated = deduper->Deduplicate(value);
339        if (deduplicated != value) {
340            elem.SetValue(deduplicated);
341        }
342    }
343}
344
345static void DeduplicateAnnotations(std::vector<AnnotationItem *> *items, ItemDeduper *annotation_deduper,
346                                   ItemDeduper *value_deduper)
347{
348    for (auto &item : *items) {
349        DeduplicateAnnotationValue(item, value_deduper);
350        auto *deduplicated = annotation_deduper->Deduplicate(item);
351        if (deduplicated != item) {
352            item = deduplicated;
353        }
354    }
355}
356
357void ItemContainer::DeduplicateAnnotations()
358{
359    ItemDeduper value_deduper;
360    ItemDeduper annotation_deduper;
361
362    for (auto &p : class_map_) {
363        auto *item = p.second;
364        if (item->IsForeign()) {
365            continue;
366        }
367
368        auto *class_item = static_cast<ClassItem *>(item);
369
370        panda_file::DeduplicateAnnotations(class_item->GetRuntimeAnnotations(), &annotation_deduper, &value_deduper);
371        panda_file::DeduplicateAnnotations(class_item->GetAnnotations(), &annotation_deduper, &value_deduper);
372        panda_file::DeduplicateAnnotations(class_item->GetRuntimeTypeAnnotations(), &annotation_deduper,
373                                           &value_deduper);
374        panda_file::DeduplicateAnnotations(class_item->GetTypeAnnotations(), &annotation_deduper, &value_deduper);
375
376        class_item->VisitMethods([&annotation_deduper, &value_deduper](BaseItem *param_item) {
377            auto *method_item = static_cast<MethodItem *>(param_item);
378            panda_file::DeduplicateAnnotations(method_item->GetRuntimeAnnotations(), &annotation_deduper,
379                                               &value_deduper);
380            panda_file::DeduplicateAnnotations(method_item->GetAnnotations(), &annotation_deduper, &value_deduper);
381            panda_file::DeduplicateAnnotations(method_item->GetRuntimeTypeAnnotations(), &annotation_deduper,
382                                               &value_deduper);
383            panda_file::DeduplicateAnnotations(method_item->GetTypeAnnotations(), &annotation_deduper, &value_deduper);
384            return true;
385        });
386
387        class_item->VisitFields([&annotation_deduper, &value_deduper](BaseItem *param_item) {
388            auto *field_item = static_cast<FieldItem *>(param_item);
389            panda_file::DeduplicateAnnotations(field_item->GetRuntimeAnnotations(), &annotation_deduper,
390                                               &value_deduper);
391            panda_file::DeduplicateAnnotations(field_item->GetAnnotations(), &annotation_deduper, &value_deduper);
392            panda_file::DeduplicateAnnotations(field_item->GetRuntimeTypeAnnotations(), &annotation_deduper,
393                                               &value_deduper);
394            panda_file::DeduplicateAnnotations(field_item->GetTypeAnnotations(), &annotation_deduper, &value_deduper);
395            return true;
396        });
397    }
398}
399
400void ItemContainer::DeduplicateItems(bool computeLayout)
401{
402    if (computeLayout) {
403        ComputeLayout();
404    }
405    DeduplicateCodeAndDebugInfo();
406    DeduplicateAnnotations();
407}
408
409static bool Compare(const std::unique_ptr<BaseItem> &item1, const std::unique_ptr<BaseItem> &item2)
410{
411    return item1->GetReLayoutRank() > item2->GetReLayoutRank();
412}
413
414void ItemContainer::ReLayout()
415{
416    for (auto &item : items_) {
417        if (!item->NeedsEmit()) {
418            continue;
419        }
420
421        /* Because only class items and func_main_0 will be accessed in runtime's initialization,
422         * the items in abc will be arranged in following order to increase cache hit rate:
423         *     class items -> string items(for field name) -> other items
424         */
425        switch (item->GetItemType()) {
426            case ItemTypes::CLASS_ITEM: {
427                item->SetReLayoutRank(ItemRank::CLASS_ITEM_RANK);
428                break;
429            }
430            case ItemTypes::STRING_ITEM: {
431                item->SetReLayoutRank(ItemRank::STRING_ITEM_RANK);
432                break;
433            }
434            default: {
435                break;
436            }
437        }
438    }
439
440    items_.sort(Compare);
441}
442
443uint32_t ItemContainer::ComputeLayout()
444{
445    const auto bc_version = GetVersionByApi(ItemContainer::GetApi(), ItemContainer::GetSubApi());
446    uint32_t original_offset = 0;
447    uint32_t num_classes = class_map_.size();
448    uint32_t num_literalarrays = literalarray_map_.size();
449    uint32_t class_idx_offset = sizeof(File::Header);
450    uint32_t cur_offset = 0;
451    if (ContainsLiteralArrayInHeader(bc_version.value())) {
452        cur_offset = class_idx_offset + (num_classes + num_literalarrays) * ID_SIZE;
453    } else {
454        cur_offset = class_idx_offset + (num_classes * ID_SIZE);
455    }
456    items_round_up_size_.clear();
457    foreign_item_roundup_size_ = 0;
458
459    UpdateOrderIndexes();
460
461    RebuildIndexSection();
462    RebuildLineNumberProgramIndex();
463
464    index_section_item_.SetOffset(cur_offset);
465    index_section_item_.ComputeLayout();
466    cur_offset += index_section_item_.GetSize();
467
468    for (auto &item : foreign_items_) {
469        original_offset = cur_offset;
470        cur_offset = RoundUp(cur_offset, item->Alignment());
471        foreign_item_roundup_size_ += CalculateRoundUpSize(original_offset, cur_offset);
472        item->SetOffset(cur_offset);
473        item->ComputeLayout();
474        cur_offset += item->GetSize();
475    }
476
477    for (auto &item : items_) {
478        const auto &name = item->GetName();
479
480        if (!item->NeedsEmit()) {
481            continue;
482        }
483
484        original_offset = cur_offset;
485        cur_offset = RoundUp(cur_offset, item->Alignment());
486        items_round_up_size_[name] += CalculateRoundUpSize(original_offset, cur_offset);
487        item->SetOffset(cur_offset);
488        item->ComputeLayout();
489        cur_offset += item->GetSize();
490    }
491
492    // Line number program should be last because it's size is known only after deduplication
493    original_offset = cur_offset;
494    cur_offset = RoundUp(cur_offset, line_number_program_index_item_.Alignment());
495    line_number_item_roundup_size_ = CalculateRoundUpSize(original_offset, cur_offset);
496    line_number_program_index_item_.SetOffset(cur_offset);
497    line_number_program_index_item_.ComputeLayout();
498    cur_offset += line_number_program_index_item_.GetSize();
499
500    end_->SetOffset(cur_offset);
501
502    return cur_offset;
503}
504
505void ItemContainer::RebuildLineNumberProgramIndex()
506{
507    line_number_program_index_item_.Reset();
508    line_number_program_index_item_.UpdateItems(nullptr, nullptr);
509}
510
511void ItemContainer::RebuildIndexSection()
512{
513    index_section_item_.Reset();
514
515    for (auto &item : foreign_items_) {
516        ProcessIndexDependecies(item.get());
517    }
518
519    for (auto &item : items_) {
520        if (!item->NeedsEmit()) {
521            continue;
522        }
523
524        ProcessIndexDependecies(item.get());
525    }
526
527    if (!index_section_item_.IsEmpty()) {
528        index_section_item_.GetCurrentHeader()->SetEnd(end_);
529    }
530
531    index_section_item_.UpdateItems();
532}
533
534void ItemContainer::UpdateOrderIndexes()
535{
536    size_t idx = 0;
537
538    for (auto &item : foreign_items_) {
539        item->SetOrderIndex(idx++);
540        item->Visit([&idx](BaseItem *param_item) {
541            param_item->SetOrderIndex(idx++);
542            return true;
543        });
544    }
545
546    for (auto &item : items_) {
547        if (!item->NeedsEmit()) {
548            continue;
549        }
550
551        item->SetOrderIndex(idx++);
552        item->Visit([&idx](BaseItem *param_item) {
553            param_item->SetOrderIndex(idx++);
554            return true;
555        });
556    }
557
558    end_->SetOrderIndex(idx++);
559}
560
561void ItemContainer::ReorderItems(panda::panda_file::pgo::ProfileOptimizer *profile_opt)
562{
563    profile_opt->ProfileGuidedRelayout(items_);
564}
565
566void ItemContainer::AddIndexDependecies(BaseItem *item)
567{
568    if (index_section_item_.IsEmpty()) {
569        index_section_item_.AddHeader();
570        index_section_item_.GetCurrentHeader()->SetStart(item);
571    }
572    const auto &item_deps = item->GetIndexDependencies();
573    if (!index_section_item_.GetCurrentHeader()->Add(item_deps)) {
574        index_section_item_.GetCurrentHeader()->SetEnd(item);
575        index_section_item_.AddHeader();
576        index_section_item_.GetCurrentHeader()->SetStart(item);
577        if (!index_section_item_.GetCurrentHeader()->Add(item_deps)) {
578            LOG(FATAL, PANDAFILE) << "Cannot add " << item_deps.size() << " items to index";
579            UNREACHABLE();
580        }
581    }
582    if (item->GetName() == "method_item") {
583        ASSERT(index_section_item_.GetNumHeaders() >= 1);
584        static_cast<BaseMethodItem *>(item)->SetHeaderIndex(index_section_item_.GetNumHeaders() - 1);
585    }
586}
587
588void ItemContainer::ProcessIndexDependecies(BaseItem *item)
589{
590    AddIndexDependecies(item);
591    item->Visit([&](BaseItem *param_item) {
592        AddIndexDependecies(param_item);
593        return true;
594    });
595}
596
597bool ItemContainer::WriteHeaderIndexInfo(Writer *writer)
598{
599    if (!writer->Write<uint32_t>(class_map_.size())) {
600        return false;
601    }
602
603    if (!writer->Write<uint32_t>(sizeof(File::Header))) {
604        return false;
605    }
606
607    if (!writer->Write<uint32_t>(line_number_program_index_item_.GetNumItems())) {
608        return false;
609    }
610
611    if (!writer->Write<uint32_t>(line_number_program_index_item_.GetOffset())) {
612        return false;
613    }
614
615    const auto bc_version = GetVersionByApi(ItemContainer::GetApi(), ItemContainer::GetSubApi());
616
617    uint32_t num_literalarrays = INVALID_INDEX;
618    uint32_t literalarray_idx_offset = INVALID_OFFSET;
619    size_t index_section_off = sizeof(File::Header) + class_map_.size() * ID_SIZE;
620
621    if (ContainsLiteralArrayInHeader(bc_version.value())) {
622        num_literalarrays = literalarray_map_.size();
623        literalarray_idx_offset = sizeof(File::Header) + class_map_.size() * ID_SIZE;
624        index_section_off = literalarray_idx_offset + num_literalarrays * ID_SIZE;
625    }
626
627    if (!writer->Write<uint32_t>(num_literalarrays)) {
628        return false;
629    }
630
631    if (!writer->Write<uint32_t>(literalarray_idx_offset)) {
632        return false;
633    }
634
635    if (!writer->Write<uint32_t>(index_section_item_.GetNumHeaders())) {
636        return false;
637    }
638
639    return writer->Write<uint32_t>(index_section_off);
640}
641
642bool ItemContainer::WriteHeader(Writer *writer, ssize_t *checksum_offset)
643{
644    uint32_t file_size = ComputeLayout();
645    writer->ReserveBufferCapacity(file_size);
646
647    std::vector<uint8_t> magic;
648    magic.assign(File::MAGIC.cbegin(), File::MAGIC.cend());
649    if (!writer->WriteBytes(magic)) {
650        return false;
651    }
652
653    *checksum_offset = writer->GetOffset();
654    uint32_t checksum = 0;
655    if (!writer->Write(checksum)) {
656        return false;
657    }
658    writer->CountChecksum(true);
659
660    const auto bc_version = GetVersionByApi(ItemContainer::GetApi(), ItemContainer::GetSubApi());
661    std::vector<uint8_t> versionVec(std::begin(bc_version.value()), std::end(bc_version.value()));
662
663    if (!writer->WriteBytes(versionVec)) {
664        return false;
665    }
666
667    if (!writer->Write(file_size)) {
668        return false;
669    }
670
671    uint32_t foreign_offset = GetForeignOffset();
672    if (!writer->Write(foreign_offset)) {
673        return false;
674    }
675
676    uint32_t foreign_size = GetForeignSize();
677    if (!writer->Write(foreign_size)) {
678        return false;
679    }
680
681    return WriteHeaderIndexInfo(writer);
682}
683
684bool ItemContainer::WriteItems(Writer *writer)
685{
686    ASSERT(writer != nullptr);
687    for (auto &item : foreign_items_) {
688        if (!writer->Align(item->Alignment())) {
689            return false;
690        }
691
692        if (!item->Write(writer)) {
693            return false;
694        }
695    }
696
697    for (auto &item : items_) {
698        if (!item->NeedsEmit()) {
699            continue;
700        }
701
702        if (!writer->Align(item->Alignment())) {
703            return false;
704        }
705
706        if (!item->Write(writer)) {
707            return false;
708        }
709    }
710    return true;
711}
712
713bool ItemContainer::Write(Writer *writer, bool deduplicateItems)
714{
715    if (deduplicateItems) {
716        DeduplicateItems();
717    }
718
719    ssize_t checksum_offset = -1;
720    if (!WriteHeader(writer, &checksum_offset)) {
721        return false;
722    }
723    ASSERT(checksum_offset != -1);
724
725    // Write class idx
726
727    for (auto &entry : class_map_) {
728        if (!writer->Write(entry.second->GetOffset())) {
729            return false;
730        }
731    }
732
733    // Write literalArray idx
734
735    const auto bc_version = GetVersionByApi(ItemContainer::GetApi(), ItemContainer::GetSubApi());
736    if (ContainsLiteralArrayInHeader(bc_version.value())) {
737        for (auto &entry : literalarray_map_) {
738            if (!writer->Write(entry.second->GetOffset())) {
739                return false;
740            }
741        }
742    }
743
744    // Write index section
745
746    if (!index_section_item_.Write(writer)) {
747        return false;
748    }
749
750    if (!WriteItems(writer)) {
751        return false;
752    }
753
754    if (!writer->Align(line_number_program_index_item_.Alignment())) {
755        return false;
756    }
757
758    // Write line number program idx
759
760    if (!line_number_program_index_item_.Write(writer)) {
761        return false;
762    }
763
764    writer->CountChecksum(false);
765    writer->RewriteChecksum(checksum_offset);
766
767    return writer->FinishWrite();
768}
769
770std::map<std::string, size_t> ItemContainer::GetStat()
771{
772    std::map<std::string, size_t> stat;
773
774    DeduplicateItems();
775    ComputeLayout();
776
777    stat["header_item"] = sizeof(File::Header);
778    stat["class_idx_item"] = class_map_.size() * ID_SIZE;
779    stat["line_number_program_idx_item"] = line_number_program_index_item_.GetNumItems() * ID_SIZE
780                                           + line_number_item_roundup_size_;
781    const auto bc_version = GetVersionByApi(ItemContainer::GetApi(), ItemContainer::GetSubApi());
782    if (ContainsLiteralArrayInHeader(bc_version.value())) {
783        stat["literalarray_idx"] = literalarray_map_.size() * ID_SIZE;
784    } else {
785        stat["literalarray_idx"] = 0;
786    }
787
788    stat["index_section_item"] = index_section_item_.GetSize();
789    stat["foreign_item"] = GetForeignSize() + foreign_item_roundup_size_;
790
791    size_t num_ins = 0;
792    size_t codesize = 0;
793    for (auto &item : items_) {
794        if (!item->NeedsEmit()) {
795            continue;
796        }
797
798        const auto &name = item->GetName();
799        size_t size = item->GetSize();
800        auto it = stat.find(name);
801        if (it != stat.cend()) {
802            stat[name] += size;
803        } else if (size != 0) {
804            stat[name] = size;
805        }
806        if (name == "code_item") {
807            num_ins += static_cast<CodeItem *>(item.get())->GetNumInstructions();
808            codesize += static_cast<CodeItem *>(item.get())->GetCodeSize();
809        }
810    }
811
812    for (const auto &[name, round_up_size] : items_round_up_size_) {
813        stat[name] += round_up_size;
814    }
815    stat["instructions_number"] = num_ins;
816    stat["codesize"] = codesize;
817
818    return stat;
819}
820
821void ItemContainer::DumpItemsStat(std::ostream &os) const
822{
823    struct Stat {
824        size_t n;
825        size_t total_size;
826    };
827
828    std::map<std::string, Stat> stat;
829
830    auto collect_stat = [&stat](auto &items) {
831        for (auto &item : items) {
832            if (!item->NeedsEmit()) {
833                continue;
834            }
835
836            const auto &name = item->GetName();
837            size_t size = item->GetSize();
838            auto it = stat.find(name);
839            if (it != stat.cend()) {
840                stat[name].n += 1;
841                stat[name].total_size += size;
842            } else if (size != 0) {
843                stat[name] = {1, size};
844            }
845        }
846    };
847
848    collect_stat(foreign_items_);
849    collect_stat(items_);
850
851    for (auto &[name, elem] : stat) {
852        os << name << ":" << std::endl;
853        os << "    n          = " << elem.n << std::endl;
854        os << "    total size = " << elem.total_size << std::endl;
855    }
856}
857
858size_t ItemContainer::GetForeignOffset() const
859{
860    if (foreign_items_.empty()) {
861        return 0;
862    }
863
864    return foreign_items_.front()->GetOffset();
865}
866
867size_t ItemContainer::GetForeignSize() const
868{
869    if (foreign_items_.empty()) {
870        return 0;
871    }
872
873    size_t begin = foreign_items_.front()->GetOffset();
874    size_t end = foreign_items_.back()->GetOffset() + foreign_items_.back()->GetSize();
875
876    return end - begin;
877}
878
879bool ItemContainer::IndexHeaderItem::Write(Writer *writer)
880{
881    ASSERT(GetOffset() == writer->GetOffset());
882    ASSERT(start_ != nullptr);
883    ASSERT(start_->GetOffset() != 0);
884    ASSERT(end_ != nullptr);
885    ASSERT(end_->GetOffset() != 0);
886
887    if (!writer->Write<uint32_t>(start_->GetOffset())) {
888        return false;
889    }
890
891    if (!writer->Write<uint32_t>(end_->GetOffset())) {
892        return false;
893    }
894
895    for (auto *index_item : indexes_) {
896        if (!index_item->NeedsEmit()) {
897            // reserve [field_idx_size] | [proto_idx_size] field
898            if (!writer->Write<uint32_t>(INVALID_INDEX)) {
899                return false;
900            }
901            // reserve [field_idx_off] | [proto_idx_off] field
902            if (!writer->Write<uint32_t>(INVALID_OFFSET)) {
903                return false;
904            }
905        } else {
906            if (!writer->Write<uint32_t>(index_item->GetNumItems())) {
907                return false;
908            }
909
910            ASSERT(index_item->GetOffset() != 0);
911            if (!writer->Write<uint32_t>(index_item->GetOffset())) {
912                return false;
913            }
914        }
915    }
916
917    return true;
918}
919
920bool ItemContainer::IndexHeaderItem::Add(const std::list<IndexedItem *> &items)
921{
922    std::list<IndexedItem *> added_items;
923
924    for (auto *item : items) {
925        auto type = item->GetIndexType();
926        ASSERT(type != IndexType::NONE);
927
928        auto *index_item = IndexGetIndexByType(type);
929
930        if (index_item->Has(item)) {
931            continue;
932        }
933
934        if (!index_item->Add(item)) {
935            Remove(added_items);
936            return false;
937        }
938
939        added_items.push_back(item);
940    }
941
942    return true;
943}
944
945void ItemContainer::IndexHeaderItem::Remove(const std::list<IndexedItem *> &items)
946{
947    for (auto *item : items) {
948        auto type = item->GetIndexType();
949        ASSERT(type != IndexType::NONE);
950
951        auto *index_item = IndexGetIndexByType(type);
952        index_item->Remove(item);
953    }
954}
955
956bool ItemContainer::IndexItem::Write(Writer *writer)
957{
958    ASSERT(GetOffset() == writer->GetOffset());
959
960    if (NeedsEmit()) {
961        for (auto *item : index_) {
962            if (!writer->Write<uint32_t>(item->GetOffset())) {
963                return false;
964            }
965        }
966    }
967
968    return true;
969}
970
971ItemTypes ItemContainer::IndexItem::GetItemType() const
972{
973    switch (type_) {
974        case IndexType::CLASS:
975            return ItemTypes::CLASS_INDEX_ITEM;
976        case IndexType::METHOD_STRING_LITERAL:
977            return ItemTypes::METHOD_INDEX_ITEM;
978        case IndexType::FIELD:
979            return ItemTypes::FIELD_INDEX_ITEM;
980        case IndexType::PROTO:
981            return ItemTypes::PROTO_INDEX_ITEM;
982        case IndexType::LINE_NUMBER_PROG:
983            return ItemTypes::LINE_NUMBER_PROGRAM_INDEX_ITEM;
984        default:
985            break;
986    }
987
988    UNREACHABLE();
989}
990
991bool ItemContainer::IndexItem::Add(IndexedItem *item)
992{
993    auto size = index_.size();
994    ASSERT(size <= max_index_);
995
996    if (size == max_index_) {
997        return false;
998    }
999
1000    auto res = index_.insert(item);
1001    ASSERT(res.second);
1002
1003    return res.second;
1004}
1005
1006void ItemContainer::IndexSectionItem::AddHeader()
1007{
1008    std::vector<IndexItem *> index_items;
1009    for (size_t i = 0; i < INDEX_COUNT_16; i++) {
1010        auto type = static_cast<IndexType>(i);
1011        indexes_.emplace_back(type, MAX_INDEX_16);
1012        index_items.push_back(&indexes_.back());
1013    }
1014    headers_.emplace_back(index_items);
1015}
1016
1017size_t ItemContainer::IndexSectionItem::CalculateSize() const
1018{
1019    size_t size = headers_.size() * sizeof(File::IndexHeader);
1020    for (auto &index_item : indexes_) {
1021        size += index_item.GetSize();
1022    }
1023    return size;
1024}
1025
1026void ItemContainer::IndexSectionItem::ComputeLayout()
1027{
1028    size_t offset = GetOffset();
1029
1030    for (auto &header : headers_) {
1031        header.SetOffset(offset);
1032        header.ComputeLayout();
1033        offset += header.GetSize();
1034    }
1035
1036    for (auto &index : indexes_) {
1037        index.SetOffset(offset);
1038        index.ComputeLayout();
1039        offset += index.GetSize();
1040    }
1041}
1042
1043bool ItemContainer::IndexSectionItem::Write(Writer *writer)
1044{
1045    ASSERT(GetOffset() == writer->GetOffset());
1046
1047    for (auto &header : headers_) {
1048        if (!header.Write(writer)) {
1049            return false;
1050        }
1051    }
1052
1053    for (auto &index : indexes_) {
1054        if (!index.Write(writer)) {
1055            return false;
1056        }
1057    }
1058
1059    return true;
1060}
1061
1062ItemContainer::ProtoKey::ProtoKey(TypeItem *ret_type, const std::vector<MethodParamItem> &params)
1063{
1064    Add(ret_type);
1065    for (const auto &param : params) {
1066        Add(param.GetType());
1067    }
1068    size_t shorty_hash = std::hash<std::string>()(shorty_);
1069    size_t ret_type_hash = std::hash<TypeItem *>()(ret_type);
1070    // combine hashes of shorty and ref_types
1071    hash_ = panda::merge_hashes(shorty_hash, ret_type_hash);
1072    // combine hashes of all param types
1073    for (const auto &item : params) {
1074        size_t param_type_hash = std::hash<TypeItem *>()(item.GetType());
1075        hash_ = panda::merge_hashes(hash_, param_type_hash);
1076    }
1077}
1078
1079void ItemContainer::ProtoKey::Add(TypeItem *item)
1080{
1081    auto type = item->GetType();
1082    shorty_.append(Type::GetSignatureByTypeId(type));
1083    if (type.IsReference()) {
1084        ref_types_.push_back(item);
1085    }
1086}
1087
1088}  // namespace panda::panda_file
1089