Include (Type|Symbol)Record.h less
[lldb.git] / llvm / include / llvm / DebugInfo / CodeView / LazyRandomTypeCollection.h
1 //===- LazyRandomTypeCollection.h -------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #ifndef LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
10 #define LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
11
12 #include "llvm/ADT/ArrayRef.h"
13 #include "llvm/ADT/Optional.h"
14 #include "llvm/ADT/StringRef.h"
15 #include "llvm/DebugInfo/CodeView/TypeCollection.h"
16 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
17 #include "llvm/Support/Allocator.h"
18 #include "llvm/Support/BinaryStreamArray.h"
19 #include "llvm/Support/Error.h"
20 #include "llvm/Support/StringSaver.h"
21 #include <cstdint>
22 #include <vector>
23
24 namespace llvm {
25 namespace codeview {
26
27 /// Provides amortized O(1) random access to a CodeView type stream.
28 /// Normally to access a type from a type stream, you must know its byte
29 /// offset into the type stream, because type records are variable-lengthed.
30 /// However, this is not the way we prefer to access them.  For example, given
31 /// a symbol record one of the fields may be the TypeIndex of the symbol's
32 /// type record.  Or given a type record such as an array type, there might
33 /// be a TypeIndex for the element type.  Sequential access is perfect when
34 /// we're just dumping every entry, but it's very poor for real world usage.
35 ///
36 /// Type streams in PDBs contain an additional field which is a list of pairs
37 /// containing indices and their corresponding offsets, roughly every ~8KB of
38 /// record data.  This general idea need not be confined to PDBs though.  By
39 /// supplying such an array, the producer of a type stream can allow the
40 /// consumer much better access time, because the consumer can find the nearest
41 /// index in this array, and do a linear scan forward only from there.
42 ///
43 /// LazyRandomTypeCollection implements this algorithm, but additionally goes
44 /// one step further by caching offsets of every record that has been visited at
45 /// least once.  This way, even repeated visits of the same record will never
46 /// require more than one linear scan.  For a type stream of N elements divided
47 /// into M chunks of roughly equal size, this yields a worst case lookup time
48 /// of O(N/M) and an amortized time of O(1).
49 class LazyRandomTypeCollection : public TypeCollection {
50   using PartialOffsetArray = FixedStreamArray<TypeIndexOffset>;
51
52   struct CacheEntry {
53     CVType Type;
54     uint32_t Offset;
55     StringRef Name;
56   };
57
58 public:
59   explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
60   LazyRandomTypeCollection(StringRef Data, uint32_t RecordCountHint);
61   LazyRandomTypeCollection(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
62   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint,
63                            PartialOffsetArray PartialOffsets);
64   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint);
65
66   void reset(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
67   void reset(StringRef Data, uint32_t RecordCountHint);
68   void reset(BinaryStreamReader &Reader, uint32_t RecordCountHint);
69
70   uint32_t getOffsetOfType(TypeIndex Index);
71
72   Optional<CVType> tryGetType(TypeIndex Index);
73
74   CVType getType(TypeIndex Index) override;
75   StringRef getTypeName(TypeIndex Index) override;
76   bool contains(TypeIndex Index) override;
77   uint32_t size() override;
78   uint32_t capacity() override;
79   Optional<TypeIndex> getFirst() override;
80   Optional<TypeIndex> getNext(TypeIndex Prev) override;
81   bool replaceType(TypeIndex &Index, CVType Data, bool Stabilize) override;
82
83 private:
84   Error ensureTypeExists(TypeIndex Index);
85   void ensureCapacityFor(TypeIndex Index);
86
87   Error visitRangeForType(TypeIndex TI);
88   Error fullScanForType(TypeIndex TI);
89   void visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End);
90
91   /// Number of actual records.
92   uint32_t Count = 0;
93
94   /// The largest type index which we've visited.
95   TypeIndex LargestTypeIndex = TypeIndex::None();
96
97   BumpPtrAllocator Allocator;
98   StringSaver NameStorage;
99
100   /// The type array to allow random access visitation of.
101   CVTypeArray Types;
102
103   std::vector<CacheEntry> Records;
104
105   /// An array of index offsets for the given type stream, allowing log(N)
106   /// lookups of a type record by index.  Similar to KnownOffsets but only
107   /// contains offsets for some type indices, some of which may not have
108   /// ever been visited.
109   PartialOffsetArray PartialOffsets;
110 };
111
112 } // end namespace codeview
113 } // end namespace llvm
114
115 #endif // LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H