1//===----------------------------------------------------------------------===//
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#include "llvm/CAS/NamedValuesSchema.h"
10#include "llvm/Support/Endian.h"
11#include "llvm/Support/EndianStream.h"
12#include "llvm/Support/StringSaver.h"
13
14using namespace llvm;
15using namespace llvm::cas;
16
17char NamedValuesSchema::ID = 0;
18constexpr StringLiteral NamedValuesSchema::SchemaName;
19
20void NamedValuesSchema::anchor() {}
21
22bool NamedValuesSchema::isNode(const ObjectProxy &Node) const {
23 // Load the first ref to check its content.
24 if (Node.getNumReferences() < 1)
25 return false;
26
27 auto FirstRef = Node.getReference(I: 0);
28 return FirstRef == *NamedValuesKindRef;
29}
30
31NamedValuesSchema::NamedValuesSchema(cas::ObjectStore &CAS, Error &E)
32 : NamedValuesSchema::RTTIExtends(CAS) {
33 ErrorAsOutParameter EAOP(E);
34 auto Kind = CAS.storeFromString(Refs: {}, String: SchemaName);
35 if (!Kind) {
36 E = Kind.takeError();
37 return;
38 }
39 NamedValuesKindRef = *Kind;
40}
41
42Expected<NamedValuesSchema> NamedValuesSchema::create(ObjectStore &CAS) {
43 Error E = Error::success();
44 NamedValuesSchema S(CAS, E);
45 if (E)
46 return std::move(E);
47 return S;
48}
49
50size_t NamedValuesSchema::getNumEntries(NamedValuesProxy Values) const {
51 return Values.getNumReferences() - 1;
52}
53
54Error NamedValuesSchema::forEachEntry(
55 NamedValuesProxy Values,
56 function_ref<Error(const NamedValuesEntry &)> Callback) const {
57 for (size_t I = 0, IE = getNumEntries(Values); I != IE; ++I)
58 if (Error E = Callback(loadEntry(Values, I)))
59 return E;
60
61 return Error::success();
62}
63
64NamedValuesEntry NamedValuesSchema::loadEntry(NamedValuesProxy Values,
65 size_t I) const {
66 StringRef Name = Values.getName(I);
67 auto ObjectRef = Values.getReference(I: I + 1);
68
69 return {Name, ObjectRef};
70}
71
72std::optional<size_t> NamedValuesSchema::lookupEntry(NamedValuesProxy Values,
73 StringRef Name) const {
74 size_t NumNames = getNumEntries(Values);
75 if (!NumNames)
76 return std::nullopt;
77
78 // Start with a binary search, if there are enough entries.
79 // FIXME: MaxLinearSearchSize is a heuristic and not optimized.
80 const size_t MaxLinearSearchSize = 4;
81 size_t Last = NumNames;
82 size_t First = 0;
83 while (Last - First > MaxLinearSearchSize) {
84 auto I = First + (Last - First) / 2;
85 StringRef NameI = Values.getName(I);
86 switch (Name.compare(RHS: NameI)) {
87 case 0:
88 return I;
89 case -1:
90 Last = I;
91 break;
92 case 1:
93 First = I + 1;
94 break;
95 }
96 }
97
98 // Use a linear search for small list.
99 for (; First != Last; ++First)
100 if (Name == Values.getName(I: First))
101 return First;
102
103 return std::nullopt;
104}
105
106Expected<NamedValuesProxy> NamedValuesSchema::load(ObjectRef Object) const {
107 auto Node = CAS.getProxy(Ref: Object);
108 if (!Node)
109 return Node.takeError();
110
111 return load(Object: *Node);
112}
113
114Expected<NamedValuesProxy> NamedValuesSchema::load(ObjectProxy Object) const {
115 if (!isNode(Node: Object))
116 return createStringError(EC: inconvertibleErrorCode(),
117 S: "object does not conform to NamedValuesSchema");
118
119 return NamedValuesProxy(*this, Object);
120}
121
122Expected<NamedValuesProxy>
123NamedValuesSchema::construct(ArrayRef<NamedValuesEntry> Entries) {
124 // ScratchPad for output.
125 SmallString<256> Data;
126 SmallVector<ObjectRef, 16> Refs;
127 Refs.push_back(Elt: *NamedValuesKindRef);
128
129 // Ensure a stable order for entries and ignore name collisions.
130 SmallVector<NamedValuesEntry> Sorted(Entries);
131 llvm::stable_sort(Range&: Sorted);
132
133 if (llvm::unique(R&: Sorted) != Sorted.end())
134 return createStringError(Fmt: "entry names are not unique");
135
136 raw_svector_ostream OS(Data);
137 support::endian::Writer Writer(OS, endianness::little);
138 // Encode the entries in the Data. The layout of the named values schema
139 // object is:
140 // * Name offset table: The offset of in the data blob for where to find the
141 // string. It has N + 1 entries and you can find the name of n-th entry at
142 // offset[n] -> offset[n+1]. Each offset is encoded as little-endian
143 // uint32_t.
144 // * Object: ObjectRef for each entry is at n + 1 refs for the object (with
145 // the first one being the named value kind ID).
146
147 // Write Name.
148 // The start of the string table index.
149 uint32_t StrIdx = sizeof(uint32_t) * (Sorted.size() + 1);
150 for (auto &Entry : Sorted) {
151 Writer.write(Val: StrIdx);
152 StrIdx += Entry.Name.size();
153
154 // Append refs.
155 Refs.push_back(Elt: Entry.Ref);
156 }
157 // Write the end index for the last string.
158 Writer.write(Val: StrIdx);
159
160 // Write names in the end of the block.
161 for (auto &Entry : Sorted)
162 OS << Entry.Name;
163
164 auto Proxy = CAS.createProxy(Refs, Data);
165 if (!Proxy)
166 return Proxy.takeError();
167
168 return NamedValuesProxy(*this, *Proxy);
169}
170
171void NamedValuesSchema::Builder::add(StringRef Name, ObjectRef Ref) {
172 StringSaver Saver(Alloc);
173 Nodes.emplace_back(Args: Saver.save(S: Name), Args&: Ref);
174}
175
176Expected<NamedValuesProxy> NamedValuesSchema::Builder::build() {
177 auto Schema = NamedValuesSchema::create(CAS);
178 if (!Schema)
179 return Schema.takeError();
180 return Schema->construct(Entries: Nodes);
181}
182
183StringRef NamedValuesProxy::getName(size_t I) const {
184 uint32_t StartIdx =
185 support::endian::read32le(P: getData().data() + sizeof(uint32_t) * I);
186 uint32_t EndIdx =
187 support::endian::read32le(P: getData().data() + sizeof(uint32_t) * (I + 1));
188
189 return StringRef(getData().data() + StartIdx, EndIdx - StartIdx);
190}
191