1//===- EntityLinker.cpp ----------------------------------------*- 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#include "clang/Analysis/Scalable/EntityLinker/EntityLinker.h"
10#include "clang/Analysis/Scalable/EntityLinker/EntitySummaryEncoding.h"
11#include "clang/Analysis/Scalable/EntityLinker/TUSummaryEncoding.h"
12#include "clang/Analysis/Scalable/Model/EntityLinkage.h"
13#include "clang/Analysis/Scalable/Model/EntityName.h"
14#include "clang/Analysis/Scalable/Support/ErrorBuilder.h"
15#include "clang/Analysis/Scalable/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 &EntityNamespace,
52 EntityLinkage::LinkageType Linkage) {
53 switch (Linkage) {
54 case EntityLinkage::LinkageType::None:
55 case EntityLinkage::LinkageType::Internal:
56 return EntityNamespace.makeQualified(Namespace: LUNamespace);
57 case EntityLinkage::LinkageType::External:
58 return NestedBuildNamespace(LUNamespace);
59 }
60
61 llvm_unreachable("Unhandled EntityLinkage::LinkageType variant");
62}
63
64EntityId EntityLinker::resolveEntity(const EntityName &OldName,
65 const EntityLinkage &Linkage) {
66 NestedBuildNamespace NewNamespace = resolveNamespace(
67 LUNamespace: Output.LUNamespace, EntityNamespace: OldName.Namespace, Linkage: Linkage.getLinkage());
68
69 EntityName NewName(OldName.USR, OldName.Suffix, NewNamespace);
70
71 // NewId construction will always return a fresh id for `None` and `Internal`
72 // linkage entities since their namespaces will be different even if their
73 // names clash. For `External` linkage entities with identical names this
74 // function will return the id assigned at the first insertion.
75 EntityId NewId = Output.IdTable.getId(Name: NewName);
76
77 auto [_, Inserted] = Output.LinkageTable.try_emplace(k: NewId, args: Linkage);
78 if (!Inserted) {
79 // Insertion failure for `None` and `Internal` linkage is a fatal error
80 // because these entities have unique namespaces and should never collide.
81 // `External` linkage entities may collide.
82 if (Linkage.getLinkage() == EntityLinkage::LinkageType::None ||
83 Linkage.getLinkage() == EntityLinkage::LinkageType::Internal) {
84 ErrorBuilder::fatal(Fmt: ErrorMessages::EntityAlreadyExistsInLinkageTable,
85 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals&: NewId,
86 ArgVals: Linkage);
87 }
88 }
89
90 return NewId;
91}
92
93std::map<EntityId, EntityId>
94EntityLinker::resolve(const TUSummaryEncoding &Summary) {
95 std::map<EntityId, EntityId> EntityResolutionTable;
96
97 Summary.IdTable.forEach(Callback: [&](const EntityName &OldName, const EntityId OldId) {
98 auto Iter = Summary.LinkageTable.find(x: OldId);
99 if (Iter == Summary.LinkageTable.end()) {
100 ErrorBuilder::fatal(Fmt: ErrorMessages::MissingLinkageInformation,
101 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: OldId);
102 }
103
104 const EntityLinkage &Linkage = Iter->second;
105
106 EntityId NewId = resolveEntity(OldName, Linkage);
107
108 auto [_, Inserted] = EntityResolutionTable.insert(x: {OldId, NewId});
109 if (!Inserted) {
110 ErrorBuilder::fatal(Fmt: ErrorMessages::DuplicateEntityIdInTUSummary,
111 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: OldId);
112 }
113 });
114
115 return EntityResolutionTable;
116}
117
118std::vector<EntitySummaryEncoding *>
119EntityLinker::merge(TUSummaryEncoding &Summary,
120 const std::map<EntityId, EntityId> &EntityResolutionTable) {
121 std::vector<EntitySummaryEncoding *> PatchTargets;
122
123 for (auto &[SN, DataMap] : Summary.Data) {
124 auto &OutputSummaryData = Output.Data[SN];
125
126 for (auto &[OldId, ES] : DataMap) {
127 auto Iter = EntityResolutionTable.find(x: OldId);
128 if (Iter == EntityResolutionTable.end()) {
129 ErrorBuilder::fatal(Fmt: ErrorMessages::EntityNotFoundInResolutionTable,
130 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: OldId);
131 }
132
133 const auto NewId = Iter->second;
134
135 auto [It, Inserted] = OutputSummaryData.try_emplace(k: NewId, args: std::move(ES));
136
137 if (Inserted) {
138 PatchTargets.push_back(x: It->second.get());
139 } else {
140 // Safe to retrieve linkage using .at since the resolve step ensures
141 // linkage information is always present for every OldId.
142 auto Linkage = Summary.LinkageTable.at(k: OldId);
143
144 // Insertion should never fail for `None` and `Internal` linkage
145 // entities because these entities will have different namespaces across
146 // TUs even if their names match.
147 if (Linkage.getLinkage() == EntityLinkage::LinkageType::None ||
148 Linkage.getLinkage() == EntityLinkage::LinkageType::Internal) {
149 ErrorBuilder::fatal(
150 Fmt: ErrorMessages::FailedToInsertEntityIntoOutputSummary,
151 ArgVals: ErrorMessages::EntityLinkerFatalErrorPrefix, ArgVals: NewId, ArgVals&: Linkage, ArgVals: SN);
152 }
153
154 // TODO: Insertion is expected to fail for duplicate occurrences of
155 // `External` linkage entities. Report these cases in a "debug" mode to
156 // help debug potential ODR violations.
157 }
158 }
159 }
160
161 return PatchTargets;
162}
163
164void EntityLinker::patch(
165 const std::vector<EntitySummaryEncoding *> &PatchTargets,
166 const std::map<EntityId, EntityId> &EntityResolutionTable) {
167 for (auto *PatchTarget : PatchTargets) {
168 assert(PatchTarget && "EntityLinker::patch: Patch target cannot be null");
169 PatchTarget->patch(EntityResolutionTable);
170 }
171}
172
173llvm::Error EntityLinker::link(std::unique_ptr<TUSummaryEncoding> Summary) {
174 auto [_, Inserted] = ProcessedTUNamespaces.insert(x: Summary->TUNamespace);
175 if (!Inserted) {
176 return ErrorBuilder::create(EC: std::errc::invalid_argument,
177 Fmt: ErrorMessages::DuplicateTUNamespace,
178 ArgVals&: Summary->TUNamespace)
179 .build();
180 }
181
182 TUSummaryEncoding &SummaryRef = *Summary;
183
184 auto EntityResolutionTable = resolve(Summary: SummaryRef);
185 auto PatchTargets = merge(Summary&: SummaryRef, EntityResolutionTable);
186 patch(PatchTargets, EntityResolutionTable);
187
188 return llvm::Error::success();
189}
190