1//===- EntityLinker.cpp ---------------------------------------------------===//
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 "clang/ScalableStaticAnalysis/Core/EntityLinker/EntityLinker.h"
10#include "clang/ScalableStaticAnalysis/Core/EntityLinker/EntitySummaryEncoding.h"
11#include "clang/ScalableStaticAnalysis/Core/EntityLinker/MultiArchStaticLibrary.h"
12#include "clang/ScalableStaticAnalysis/Core/EntityLinker/StaticLibrary.h"
13#include "clang/ScalableStaticAnalysis/Core/EntityLinker/TUSummaryEncoding.h"
14#include "clang/ScalableStaticAnalysis/Core/Model/EntityLinkage.h"
15#include "clang/ScalableStaticAnalysis/Core/Model/EntityName.h"
16#include "clang/ScalableStaticAnalysis/Core/Support/ErrorBuilder.h"
17#include "clang/ScalableStaticAnalysis/Core/Support/FormatProviders.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/StringExtras.h"
20#include <cassert>
21
22using namespace clang::ssaf;
23
24//===----------------------------------------------------------------------===//
25// Error Message Constants
26//===----------------------------------------------------------------------===//
27
28namespace ErrorMessages {
29
30static constexpr const char *EntityLinkerFatalErrorPrefix =
31 "EntityLinker: Corrupted TUSummary or logic bug";
32
33static constexpr const char *EntityAlreadyExistsInLinkageTable =
34 "{0} - {1} with {2} already exists in LUSummary";
35
36static constexpr const char *MissingLinkageInformation =
37 "{0} - {1} missing linkage information in TUSummary";
38
39static constexpr const char *DuplicateEntityIdInTUSummary =
40 "{0} - Duplicate {1} in EntityResolutionTable";
41
42static constexpr const char *EntityNotFoundInResolutionTable =
43 "{0} - {1} not found in EntityResolutionTable";
44
45static constexpr const char *FailedToInsertEntityIntoOutputSummary =
46 "{0} - Failed to insert data for {1} with {2} against {3} to LUSummary";
47
48static constexpr const char *DuplicateTUNamespace =
49 "failed to link TU summary: duplicate {0}";
50
51static constexpr const char *LinkingStaticLibraryMember =
52 "failed to link member {0} of static library {1}";
53
54static constexpr const char *MismatchedTargetTriple =
55 "target triple '{0}' of {1} does not match link unit target triple '{2}'";
56
57static constexpr const char *NoMemberForTargetTriple =
58 "multi-arch static library {0} has no member for target triple '{1}' "
59 "(available: {2})";
60
61} // namespace ErrorMessages
62
63NestedBuildNamespace
64clang::ssaf::resolveNamespace(const NestedBuildNamespace &LUNamespace,
65 const NestedBuildNamespace &TUNamespace,
66 const NestedBuildNamespace &EntityNamespace,
67 EntityLinkageType Linkage) {
68 switch (Linkage) {
69 case EntityLinkageType::None:
70 case EntityLinkageType::Internal:
71 // Qualify with the TU namespace first (to disambiguate across TUs),
72 // then with the LU namespace.
73 return EntityNamespace.makeQualified(Namespace: TUNamespace)
74 .makeQualified(Namespace: LUNamespace);
75 case EntityLinkageType::External:
76 return NestedBuildNamespace(LUNamespace);
77 }
78
79 llvm_unreachable("Unhandled EntityLinkageType variant");
80}
81
82EntityId EntityLinker::resolveEntity(const EntityName &OldName,
83 const EntityLinkage &Linkage,
84 const NestedBuildNamespace &TUNamespace) {
85 NestedBuildNamespace NewNamespace = resolveNamespace(
86 LUNamespace: Output.LUNamespace, TUNamespace, EntityNamespace: OldName.Namespace, Linkage: Linkage.getLinkage());
87
88 EntityName NewName(OldName.USR, OldName.Suffix, NewNamespace);
89
90 // NewId construction will always return a fresh id for `None` and `Internal`
91 // linkage entities since their namespaces will be different even if their
92 // names clash. For `External` linkage entities with identical names this
93 // function will return the id assigned at the first insertion.
94 EntityId NewId = Output.IdTable.getId(Name: NewName);
95
96 auto [_, Inserted] = Output.LinkageTable.try_emplace(k: NewId, args: Linkage);
97 if (!Inserted) {
98 // Insertion failure for `None` and `Internal` linkage is a fatal error
99 // because these entities have unique namespaces and should never collide.
100 // `External` linkage entities may collide.
101 if (Linkage.getLinkage() == EntityLinkageType::None ||
102 Linkage.getLinkage() == EntityLinkageType::Internal) {
103 ErrorBuilder::fatal(Fmt: ErrorMessages::EntityAlreadyExistsInLinkageTable,
104 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals&: NewId,
105 ArgVals: Linkage);
106 }
107 }
108
109 return NewId;
110}
111
112std::map<EntityId, EntityId>
113EntityLinker::resolve(const TUSummaryEncoding &Summary) {
114 std::map<EntityId, EntityId> EntityResolutionTable;
115
116 Summary.IdTable.forEach(Callback: [&](const EntityName &OldName, const EntityId OldId) {
117 auto Iter = Summary.LinkageTable.find(x: OldId);
118 if (Iter == Summary.LinkageTable.end()) {
119 ErrorBuilder::fatal(Fmt: ErrorMessages::MissingLinkageInformation,
120 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: OldId);
121 }
122
123 const EntityLinkage &Linkage = Iter->second;
124
125 EntityId NewId = resolveEntity(OldName, Linkage,
126 TUNamespace: NestedBuildNamespace(Summary.TUNamespace));
127
128 auto [_, Inserted] = EntityResolutionTable.insert(x: {OldId, NewId});
129 if (!Inserted) {
130 ErrorBuilder::fatal(Fmt: ErrorMessages::DuplicateEntityIdInTUSummary,
131 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: OldId);
132 }
133 });
134
135 return EntityResolutionTable;
136}
137
138std::vector<EntitySummaryEncoding *>
139EntityLinker::merge(TUSummaryEncoding &Summary,
140 const std::map<EntityId, EntityId> &EntityResolutionTable) {
141 std::vector<EntitySummaryEncoding *> PatchTargets;
142
143 for (auto &[SN, DataMap] : Summary.Data) {
144 auto &OutputSummaryData = Output.Data[SN];
145
146 for (auto &[OldId, ES] : DataMap) {
147 auto Iter = EntityResolutionTable.find(x: OldId);
148 if (Iter == EntityResolutionTable.end()) {
149 ErrorBuilder::fatal(Fmt: ErrorMessages::EntityNotFoundInResolutionTable,
150 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: OldId);
151 }
152
153 const auto NewId = Iter->second;
154
155 auto [It, Inserted] = OutputSummaryData.try_emplace(k: NewId, args: std::move(ES));
156
157 if (Inserted) {
158 PatchTargets.push_back(x: It->second.get());
159 } else {
160 // Safe to retrieve linkage using .at since the resolve step ensures
161 // linkage information is always present for every OldId.
162 auto Linkage = Summary.LinkageTable.at(k: OldId);
163
164 // Insertion should never fail for `None` and `Internal` linkage
165 // entities because these entities will have different namespaces across
166 // TUs even if their names match.
167 if (Linkage.getLinkage() == EntityLinkageType::None ||
168 Linkage.getLinkage() == EntityLinkageType::Internal) {
169 ErrorBuilder::fatal(
170 Fmt: ErrorMessages::FailedToInsertEntityIntoOutputSummary,
171 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: NewId, ArgVals&: Linkage, ArgVals: SN);
172 }
173
174 // TODO: Insertion is expected to fail for duplicate occurrences of
175 // `External` linkage entities. Report these cases in a "debug" mode to
176 // help debug potential ODR violations.
177 }
178 }
179 }
180
181 return PatchTargets;
182}
183
184llvm::Error
185EntityLinker::patch(const std::vector<EntitySummaryEncoding *> &PatchTargets,
186 const std::map<EntityId, EntityId> &EntityResolutionTable) {
187 for (auto *PatchTarget : PatchTargets) {
188 assert(PatchTarget && "EntityLinker::patch: Patch target cannot be null");
189
190 if (auto Err = PatchTarget->patch(EntityResolutionTable)) {
191 return Err;
192 }
193 }
194 return llvm::Error::success();
195}
196
197llvm::Error
198EntityLinker::checkTargetTriple(const llvm::Triple &TargetTriple,
199 const BuildNamespace &InputNamespace) const {
200 if (TargetTriple != Output.TargetTriple) {
201 return ErrorBuilder::create(EC: std::errc::invalid_argument,
202 Fmt: ErrorMessages::MismatchedTargetTriple,
203 ArgVals: TargetTriple, ArgVals: InputNamespace,
204 ArgVals: Output.TargetTriple)
205 .build();
206 }
207 return llvm::Error::success();
208}
209
210llvm::Error EntityLinker::link(std::unique_ptr<TUSummaryEncoding> Summary) {
211 if (auto Err =
212 checkTargetTriple(TargetTriple: Summary->TargetTriple, InputNamespace: Summary->TUNamespace)) {
213 return Err;
214 }
215
216 auto [_, Inserted] = ProcessedTUNamespaces.insert(x: Summary->TUNamespace);
217 if (!Inserted) {
218 return ErrorBuilder::create(EC: std::errc::invalid_argument,
219 Fmt: ErrorMessages::DuplicateTUNamespace,
220 ArgVals&: Summary->TUNamespace)
221 .build();
222 }
223
224 TUSummaryEncoding &SummaryRef = *Summary;
225
226 auto EntityResolutionTable = resolve(Summary: SummaryRef);
227 auto PatchTargets = merge(Summary&: SummaryRef, EntityResolutionTable);
228 return patch(PatchTargets, EntityResolutionTable);
229}
230
231llvm::Error EntityLinker::link(std::unique_ptr<StaticLibrary> Library) {
232 if (auto Err = checkTargetTriple(TargetTriple: Library->TargetTriple, InputNamespace: Library->Namespace)) {
233 return Err;
234 }
235
236 while (!Library->Members.empty()) {
237 auto Node = Library->Members.extract(pos: Library->Members.begin());
238 const BuildNamespace MemberNamespace = Node.value()->TUNamespace;
239
240 if (auto Err = link(Summary: std::move(Node.value()))) {
241 return ErrorBuilder::wrap(E: std::move(Err))
242 .context(Fmt: ErrorMessages::LinkingStaticLibraryMember, ArgVals: MemberNamespace,
243 ArgVals&: Library->Namespace)
244 .build();
245 }
246 }
247
248 return llvm::Error::success();
249}
250
251llvm::Error
252EntityLinker::link(std::unique_ptr<MultiArchStaticLibrary> Library) {
253 auto MatchingMember = llvm::find_if(
254 Range&: Library->Members, P: [this](const std::unique_ptr<StaticLibrary> &Member) {
255 return Member->TargetTriple == Output.TargetTriple;
256 });
257
258 if (MatchingMember == Library->Members.end()) {
259 auto TargetTriples = llvm::map_range(
260 C&: Library->Members, F: [](const std::unique_ptr<StaticLibrary> &Member) {
261 return llvm::Triple::normalize(Str: Member->TargetTriple.str());
262 });
263 std::string Available = Library->Members.empty()
264 ? std::string("none")
265 : llvm::join(R&: TargetTriples, Separator: ", ");
266
267 return ErrorBuilder::create(EC: std::errc::invalid_argument,
268 Fmt: ErrorMessages::NoMemberForTargetTriple,
269 ArgVals&: Library->Namespace, ArgVals&: Output.TargetTriple,
270 ArgVals&: Available)
271 .build();
272 }
273
274 return link(Library: std::move(Library->Members.extract(pos: MatchingMember).value()));
275}
276