1//===- TypeConstrainedPointers.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// Implementation of the Type Constrained Pointers analysis, including
10//
11// a) the Extractor implementation collecting pointer entities that shall retain
12// their types
13//
14// b) the WPA implementation that simply groups extracted summaries into a
15// TypeConstrainedPointersAnalysisResult that other analysis can use.
16//
17// c) serialization implementations
18//
19//===----------------------------------------------------------------------===//
20
21#include "clang/ScalableStaticAnalysis/Analyses/TypeConstrainedPointers/TypeConstrainedPointers.h"
22#include "../SSAFAnalysesCommon.h"
23#include "clang/AST/ASTContext.h"
24#include "clang/AST/Decl.h"
25#include "clang/AST/DeclCXX.h"
26#include "clang/AST/Type.h"
27#include "clang/Basic/OperatorKinds.h"
28#include "clang/ScalableStaticAnalysis/Core/Model/EntityId.h"
29#include "clang/ScalableStaticAnalysis/Core/Serialization/JSONFormat.h"
30#include "clang/ScalableStaticAnalysis/Core/TUSummary/ExtractorRegistry.h"
31#include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryExtractor.h"
32#include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisRegistry.h"
33#include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisResult.h"
34#include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/SummaryAnalysis.h"
35#include "llvm/ADT/StringRef.h"
36#include "llvm/Support/Error.h"
37#include "llvm/Support/JSON.h"
38#include <memory>
39#include <optional>
40#include <utility>
41#include <vector>
42
43using namespace clang;
44using namespace ssaf;
45
46namespace {
47
48// Extracts pointer entities that must retain their pointer type.
49//
50// From `operator new` / `operator delete` overloads:
51// 1 the return entity of `operator new` overloads;
52// 2 the second parameter of `operator new(size_t, void*)` representing the
53// pointer to the memory area at which to initialize the object;
54// 3 the first parameter of `operator delete` overloads representing the
55// pointer to the memory block to deallocate (or a null pointer);
56// 4 the second parameter of `operator delete(void*, void*)` representing
57// the placement pointer matching the corresponding placement `new`.
58//
59// From the `main` function:
60// 5 pointer-typed parameters of `main`.
61class TypeConstrainedPointersExtractor final : public TUSummaryExtractor {
62public:
63 using TUSummaryExtractor::TUSummaryExtractor;
64
65private:
66 void HandleTranslationUnit(ASTContext &Ctx) override;
67
68 std::unique_ptr<TypeConstrainedPointersEntitySummary>
69 extractEntitySummary(const std::vector<const NamedDecl *> &Decls);
70};
71
72void TypeConstrainedPointersExtractor::HandleTranslationUnit(ASTContext &Ctx) {
73 extractAndAddSummaries(
74 Extractor&: *this, Builder&: SummaryBuilder, Ctx,
75 ExtractFn: [&](const std::vector<const NamedDecl *> &Decls) {
76 return extractEntitySummary(Decls);
77 },
78 ExtractorName: TypeConstrainedPointersEntitySummary::Name);
79}
80
81std::unique_ptr<TypeConstrainedPointersEntitySummary>
82TypeConstrainedPointersExtractor::extractEntitySummary(
83 const std::vector<const NamedDecl *> &ContributorDecls) {
84 auto Summary = std::make_unique<TypeConstrainedPointersEntitySummary>();
85 auto Matcher = [&Summary, this](const DynTypedNode &Node) {
86 const auto *FD = Node.get<FunctionDecl>();
87
88 if (!FD)
89 return;
90
91 OverloadedOperatorKind OO = FD->getOverloadedOperator();
92
93 switch (OO) {
94 case OO_New:
95 case OO_Array_New:
96 // Extract case 1:
97 if (auto Id = addEntityForReturn(FD))
98 Summary->Entities.insert(x: *Id);
99 break;
100 case OO_Delete:
101 case OO_Array_Delete:
102 // Extract case 3; ignore ill-formed ones (first param not a pointer).
103 if (!FD->getNumParams() || !hasPtrOrArrType(D: FD->getParamDecl(i: 0)))
104 return;
105 if (auto Id = addEntity(D: FD->getParamDecl(i: 0)))
106 Summary->Entities.insert(x: *Id);
107 break;
108 default:
109 // Extract case 5: pointer-typed parameters of main.
110 if (FD->isMain())
111 for (const ParmVarDecl *PVD : FD->parameters()) {
112 if (hasPtrOrArrType(D: PVD))
113 if (auto Id = addEntity(D: PVD))
114 Summary->Entities.insert(x: *Id);
115 }
116 return;
117 };
118 // Extract case 2 & 4: only `operator new(size_t, void*)` and
119 // `operator delete(void*, void*)` are standard-defined with a void* 2nd
120 // param; for user-defined 3+ param overloads the 2nd param type is
121 // unconstrained, so we conservatively skip them.
122 if (FD->getNumParams() == 2 && hasPtrOrArrType(D: FD->getParamDecl(i: 1))) {
123 if (auto Id = addEntity(D: FD->getParamDecl(i: 1)))
124 Summary->Entities.insert(x: *Id);
125 }
126 };
127
128 for (const NamedDecl *Decl : ContributorDecls)
129 findMatchesIn(Contributor: Decl, MatchActionRef: Matcher);
130 return Summary;
131}
132
133//===----------------------------------------------------------------------===//
134// WPA implementation
135//===----------------------------------------------------------------------===//
136class TypeConstrainedPointersAnalysis final
137 : public SummaryAnalysis<TypeConstrainedPointersAnalysisResult,
138 TypeConstrainedPointersEntitySummary> {
139public:
140 llvm::Error
141 add(EntityId, const TypeConstrainedPointersEntitySummary &Summary) override {
142 getResult().Entities.insert(first: Summary.Entities.begin(),
143 last: Summary.Entities.end());
144 return llvm::Error::success();
145 }
146};
147
148AnalysisRegistry::Add<TypeConstrainedPointersAnalysis>
149 RegisterTypeConstrainedPointersAnalysis(
150 "Whole-program set of pointer entities that "
151 "must retain their pointer type");
152
153//===----------------------------------------------------------------------===//
154// serialization implementation
155//===----------------------------------------------------------------------===//
156
157llvm::json::Object serializeImpl(const std::set<EntityId> &Set,
158 JSONFormat::EntityIdToJSONFn Fn) {
159 llvm::json::Object Result;
160 llvm::json::Array DataArray;
161
162 DataArray.reserve(S: Set.size());
163 for (const auto &Ent : Set)
164 DataArray.push_back(E: Fn(Ent));
165 Result[TypeConstrainedPointersAnalysisResult::Name] = std::move(DataArray);
166 return Result;
167}
168
169llvm::Expected<std::set<EntityId>>
170deserializeImpl(const llvm::json::Object &Data,
171 JSONFormat::EntityIdFromJSONFn Fn) {
172 const auto *DataArray =
173 Data.getArray(K: TypeConstrainedPointersAnalysisResult::Name);
174 std::set<EntityId> EntitySet;
175
176 if (!DataArray) {
177 return makeSawButExpectedError(
178 Saw: Data, Expected: "An object with a key %s",
179 ExpectedArgs: TypeConstrainedPointersAnalysisResult::Name.data());
180 }
181 for (const auto &Elt : *DataArray) {
182 const auto *EltAsObj = Elt.getAsObject();
183
184 if (!EltAsObj)
185 return makeSawButExpectedError(Saw: Elt, Expected: "an object representing EntityId");
186
187 Expected<EntityId> EntityId = Fn(*EltAsObj);
188
189 if (!EntityId)
190 return EntityId.takeError();
191
192 EntitySet.insert(x: *EntityId);
193 }
194 return EntitySet;
195}
196
197llvm::json::Object serializeSummary(const EntitySummary &S,
198 JSONFormat::EntityIdToJSONFn Fn) {
199 const auto &SS = static_cast<const TypeConstrainedPointersEntitySummary &>(S);
200 return serializeImpl(Set: SS.Entities, Fn);
201}
202
203llvm::Expected<std::unique_ptr<EntitySummary>>
204deserializeSummary(const llvm::json::Object &Data, EntityIdTable &,
205 JSONFormat::EntityIdFromJSONFn Fn) {
206 llvm::Expected<std::set<EntityId>> EntityIDSet = deserializeImpl(Data, Fn);
207
208 if (!EntityIDSet)
209 return EntityIDSet.takeError();
210
211 std::unique_ptr<TypeConstrainedPointersEntitySummary> Sum =
212 std::make_unique<TypeConstrainedPointersEntitySummary>();
213
214 Sum->Entities = std::move(*EntityIDSet);
215 return Sum;
216}
217
218struct TypeConstrainedPointersJSONFormatInfo final : JSONFormat::FormatInfo {
219 TypeConstrainedPointersJSONFormatInfo()
220 : JSONFormat::FormatInfo(
221 TypeConstrainedPointersEntitySummary::summaryName(),
222 serializeSummary, deserializeSummary) {}
223};
224
225static llvm::Registry<JSONFormat::FormatInfo>::Add<
226 TypeConstrainedPointersJSONFormatInfo>
227 RegisterTypeConstrainedPointersJSONFormatInfo(
228 TypeConstrainedPointersEntitySummary::Name,
229 "JSON Format info for TypeConstrainedPointersEntitySummary");
230
231llvm::json::Object
232serializeAnalysisResult(const TypeConstrainedPointersAnalysisResult &R,
233 JSONFormat::EntityIdToJSONFn Fn) {
234 return serializeImpl(Set: R.Entities, Fn);
235}
236
237llvm::Expected<std::unique_ptr<AnalysisResult>>
238deserializeAnalysisResult(const llvm::json::Object &Data,
239 JSONFormat::EntityIdFromJSONFn Fn) {
240 llvm::Expected<std::set<EntityId>> EntityIDSet = deserializeImpl(Data, Fn);
241
242 if (!EntityIDSet)
243 return EntityIDSet.takeError();
244
245 std::unique_ptr<TypeConstrainedPointersAnalysisResult> AR =
246 std::make_unique<TypeConstrainedPointersAnalysisResult>();
247
248 AR->Entities = std::move(*EntityIDSet);
249 return AR;
250}
251
252JSONFormat::AnalysisResultRegistry::Add<TypeConstrainedPointersAnalysisResult>
253 RegisterTypeConstrainedPointersAnalysisResultForJSON(
254 serializeAnalysisResult, deserializeAnalysisResult);
255
256} // namespace
257
258namespace clang::ssaf {
259// NOLINTNEXTLINE(misc-use-internal-linkage)
260volatile int TypeConstrainedPointersAnchorSource = 0;
261} // namespace clang::ssaf
262
263static TUSummaryExtractorRegistry::Add<TypeConstrainedPointersExtractor>
264 RegisterTypeConstrainedPointersExtractor(
265 TypeConstrainedPointersEntitySummary::Name,
266 "Extract pointer entities that must retain their pointer type");
267