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/TUSummaryEncoding.h"
12#include "clang/ScalableStaticAnalysis/Core/Model/EntityLinkage.h"
13#include "clang/ScalableStaticAnalysis/Core/Model/EntityName.h"
14#include "clang/ScalableStaticAnalysis/Core/Support/ErrorBuilder.h"
15#include "clang/ScalableStaticAnalysis/Core/Support/FormatProviders.h"
16#include <cassert>
17
18using namespace clang::ssaf;
19
20//===----------------------------------------------------------------------===//
21// Error Message Constants
22//===----------------------------------------------------------------------===//
23
24namespace ErrorMessages {
25
26static constexpr const char *EntityLinkerFatalErrorPrefix =
27 "EntityLinker: Corrupted TUSummary or logic bug";
28
29static constexpr const char *EntityAlreadyExistsInLinkageTable =
30 "{0} - {1} with {2} already exists in LUSummary";
31
32static constexpr const char *MissingLinkageInformation =
33 "{0} - {1} missing linkage information in TUSummary";
34
35static constexpr const char *DuplicateEntityIdInTUSummary =
36 "{0} - Duplicate {1} in EntityResolutionTable";
37
38static constexpr const char *EntityNotFoundInResolutionTable =
39 "{0} - {1} not found in EntityResolutionTable";
40
41static constexpr const char *FailedToInsertEntityIntoOutputSummary =
42 "{0} - Failed to insert data for {1} with {2} against {3} to LUSummary";
43
44static constexpr const char *DuplicateTUNamespace =
45 "failed to link TU summary: duplicate {0}";
46
47} // namespace ErrorMessages
48
49static NestedBuildNamespace
50resolveNamespace(const NestedBuildNamespace &LUNamespace,
51 const NestedBuildNamespace &TUNamespace,
52 const NestedBuildNamespace &EntityNamespace,
53 EntityLinkageType Linkage) {
54 switch (Linkage) {
55 case EntityLinkageType::None:
56 case EntityLinkageType::Internal:
57 // Qualify with the TU namespace first (to disambiguate across TUs),
58 // then with the LU namespace.
59 return EntityNamespace.makeQualified(Namespace: TUNamespace)
60 .makeQualified(Namespace: LUNamespace);
61 case EntityLinkageType::External:
62 return NestedBuildNamespace(LUNamespace);
63 }
64
65 llvm_unreachable("Unhandled EntityLinkageType variant");
66}
67
68EntityId EntityLinker::resolveEntity(const EntityName &OldName,
69 const EntityLinkage &Linkage,
70 const NestedBuildNamespace &TUNamespace) {
71 NestedBuildNamespace NewNamespace = resolveNamespace(
72 LUNamespace: Output.LUNamespace, TUNamespace, EntityNamespace: OldName.Namespace, Linkage: Linkage.getLinkage());
73
74 EntityName NewName(OldName.USR, OldName.Suffix, NewNamespace);
75
76 // NewId construction will always return a fresh id for `None` and `Internal`
77 // linkage entities since their namespaces will be different even if their
78 // names clash. For `External` linkage entities with identical names this
79 // function will return the id assigned at the first insertion.
80 EntityId NewId = Output.IdTable.getId(Name: NewName);
81
82 auto [_, Inserted] = Output.LinkageTable.try_emplace(k: NewId, args: Linkage);
83 if (!Inserted) {
84 // Insertion failure for `None` and `Internal` linkage is a fatal error
85 // because these entities have unique namespaces and should never collide.
86 // `External` linkage entities may collide.
87 if (Linkage.getLinkage() == EntityLinkageType::None ||
88 Linkage.getLinkage() == EntityLinkageType::Internal) {
89 ErrorBuilder::fatal(Fmt: ErrorMessages::EntityAlreadyExistsInLinkageTable,
90 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals&: NewId,
91 ArgVals: Linkage);
92 }
93 }
94
95 return NewId;
96}
97
98std::map<EntityId, EntityId>
99EntityLinker::resolve(const TUSummaryEncoding &Summary) {
100 std::map<EntityId, EntityId> EntityResolutionTable;
101
102 Summary.IdTable.forEach(Callback: [&](const EntityName &OldName, const EntityId OldId) {
103 auto Iter = Summary.LinkageTable.find(x: OldId);
104 if (Iter == Summary.LinkageTable.end()) {
105 ErrorBuilder::fatal(Fmt: ErrorMessages::MissingLinkageInformation,
106 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: OldId);
107 }
108
109 const EntityLinkage &Linkage = Iter->second;
110
111 EntityId NewId = resolveEntity(OldName, Linkage,
112 TUNamespace: NestedBuildNamespace(Summary.TUNamespace));
113
114 auto [_, Inserted] = EntityResolutionTable.insert(x: {OldId, NewId});
115 if (!Inserted) {
116 ErrorBuilder::fatal(Fmt: ErrorMessages::DuplicateEntityIdInTUSummary,
117 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: OldId);
118 }
119 });
120
121 return EntityResolutionTable;
122}
123
124std::vector<EntitySummaryEncoding *>
125EntityLinker::merge(TUSummaryEncoding &Summary,
126 const std::map<EntityId, EntityId> &EntityResolutionTable) {
127 std::vector<EntitySummaryEncoding *> PatchTargets;
128
129 for (auto &[SN, DataMap] : Summary.Data) {
130 auto &OutputSummaryData = Output.Data[SN];
131
132 for (auto &[OldId, ES] : DataMap) {
133 auto Iter = EntityResolutionTable.find(x: OldId);
134 if (Iter == EntityResolutionTable.end()) {
135 ErrorBuilder::fatal(Fmt: ErrorMessages::EntityNotFoundInResolutionTable,
136 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: OldId);
137 }
138
139 const auto NewId = Iter->second;
140
141 auto [It, Inserted] = OutputSummaryData.try_emplace(k: NewId, args: std::move(ES));
142
143 if (Inserted) {
144 PatchTargets.push_back(x: It->second.get());
145 } else {
146 // Safe to retrieve linkage using .at since the resolve step ensures
147 // linkage information is always present for every OldId.
148 auto Linkage = Summary.LinkageTable.at(k: OldId);
149
150 // Insertion should never fail for `None` and `Internal` linkage
151 // entities because these entities will have different namespaces across
152 // TUs even if their names match.
153 if (Linkage.getLinkage() == EntityLinkageType::None ||
154 Linkage.getLinkage() == EntityLinkageType::Internal) {
155 ErrorBuilder::fatal(
156 Fmt: ErrorMessages::FailedToInsertEntityIntoOutputSummary,
157 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: NewId, ArgVals&: Linkage, ArgVals: SN);
158 }
159
160 // TODO: Insertion is expected to fail for duplicate occurrences of
161 // `External` linkage entities. Report these cases in a "debug" mode to
162 // help debug potential ODR violations.
163 }
164 }
165 }
166
167 return PatchTargets;
168}
169
170llvm::Error
171EntityLinker::patch(const std::vector<EntitySummaryEncoding *> &PatchTargets,
172 const std::map<EntityId, EntityId> &EntityResolutionTable) {
173 for (auto *PatchTarget : PatchTargets) {
174 assert(PatchTarget && "EntityLinker::patch: Patch target cannot be null");
175
176 if (auto Err = PatchTarget->patch(EntityResolutionTable)) {
177 return Err;
178 }
179 }
180 return llvm::Error::success();
181}
182
183llvm::Error EntityLinker::link(std::unique_ptr<TUSummaryEncoding> Summary) {
184 auto [_, Inserted] = ProcessedTUNamespaces.insert(x: Summary->TUNamespace);
185 if (!Inserted) {
186 return ErrorBuilder::create(EC: std::errc::invalid_argument,
187 Fmt: ErrorMessages::DuplicateTUNamespace,
188 ArgVals&: Summary->TUNamespace)
189 .build();
190 }
191
192 TUSummaryEncoding &SummaryRef = *Summary;
193
194 auto EntityResolutionTable = resolve(Summary: SummaryRef);
195 auto PatchTargets = merge(Summary&: SummaryRef, EntityResolutionTable);
196 return patch(PatchTargets, EntityResolutionTable);
197}
198