1//===- DynamicTypePropagation.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// This file contains two checkers. One helps the static analyzer core to track
10// types, the other does type inference on Obj-C generics and report type
11// errors.
12//
13// Dynamic Type Propagation:
14// This checker defines the rules for dynamic type gathering and propagation.
15//
16// Generics Checker for Objective-C:
17// This checker tries to find type errors that the compiler is not able to catch
18// due to the implicit conversions that were introduced for backward
19// compatibility.
20//
21//===----------------------------------------------------------------------===//
22
23#include "clang/AST/DynamicRecursiveASTVisitor.h"
24#include "clang/AST/ParentMap.h"
25#include "clang/Basic/Builtins.h"
26#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
27#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
28#include "clang/StaticAnalyzer/Core/Checker.h"
29#include "clang/StaticAnalyzer/Core/CheckerManager.h"
30#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
31#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
32#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
33#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
34#include "llvm/ADT/STLExtras.h"
35#include <optional>
36
37using namespace clang;
38using namespace ento;
39
40// ProgramState trait - The type inflation is tracked by DynamicTypeMap. This is
41// an auxiliary map that tracks more information about generic types, because in
42// some cases the most derived type is not the most informative one about the
43// type parameters. This types that are stored for each symbol in this map must
44// be specialized.
45// TODO: In some case the type stored in this map is exactly the same that is
46// stored in DynamicTypeMap. We should no store duplicated information in those
47// cases.
48REGISTER_MAP_WITH_PROGRAMSTATE(MostSpecializedTypeArgsMap, SymbolRef,
49 const ObjCObjectPointerType *)
50
51namespace {
52class DynamicTypePropagation
53 : public CheckerFamily<check::PreCall, check::PostCall, check::DeadSymbols,
54 check::PostStmt<CastExpr>,
55 check::PostStmt<CXXNewExpr>, check::PreObjCMessage,
56 check::PostObjCMessage> {
57public:
58 // This checker family implements only one frontend, but -- unlike a simple
59 // Checker -- its backend can be enabled (by the checker DynamicTypeChecker
60 // which depends on it) without enabling the frontend.
61 CheckerFrontendWithBugType ObjCGenericsChecker{
62 "Generics", categories::CoreFoundationObjectiveC};
63
64private:
65 /// Return a better dynamic type if one can be derived from the cast.
66 const ObjCObjectPointerType *getBetterObjCType(const Expr *CastE,
67 CheckerContext &C) const;
68
69 ExplodedNode *dynamicTypePropagationOnCasts(const CastExpr *CE,
70 ProgramStateRef &State,
71 CheckerContext &C) const;
72
73 class GenericsBugVisitor : public BugReporterVisitor {
74 public:
75 GenericsBugVisitor(SymbolRef S) : Sym(S) {}
76
77 void Profile(llvm::FoldingSetNodeID &ID) const override {
78 static int X = 0;
79 ID.AddPointer(Ptr: &X);
80 ID.AddPointer(Ptr: Sym);
81 }
82
83 PathDiagnosticPieceRef VisitNode(const ExplodedNode *N,
84 BugReporterContext &BRC,
85 PathSensitiveBugReport &BR) override;
86
87 private:
88 // The tracked symbol.
89 SymbolRef Sym;
90 };
91
92 void reportGenericsBug(const ObjCObjectPointerType *From,
93 const ObjCObjectPointerType *To, ExplodedNode *N,
94 SymbolRef Sym, CheckerContext &C,
95 const Stmt *ReportedNode = nullptr) const;
96
97public:
98 void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
99 void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
100 void checkPostStmt(const CastExpr *CastE, CheckerContext &C) const;
101 void checkPostStmt(const CXXNewExpr *NewE, CheckerContext &C) const;
102 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
103 void checkPreObjCMessage(const ObjCMethodCall &M, CheckerContext &C) const;
104 void checkPostObjCMessage(const ObjCMethodCall &M, CheckerContext &C) const;
105
106 /// Identifies this checker family for debugging purposes.
107 StringRef getDebugTag() const override { return "DynamicTypePropagation"; }
108};
109
110bool isObjCClassType(QualType Type) {
111 if (const auto *PointerType = dyn_cast<ObjCObjectPointerType>(Val&: Type)) {
112 return PointerType->getObjectType()->isObjCClass();
113 }
114 return false;
115}
116
117struct RuntimeType {
118 const ObjCObjectType *Type = nullptr;
119 bool Precise = false;
120
121 operator bool() const { return Type != nullptr; }
122};
123
124RuntimeType inferReceiverType(const ObjCMethodCall &Message,
125 CheckerContext &C) {
126 const ObjCMessageExpr *MessageExpr = Message.getOriginExpr();
127
128 // Check if we can statically infer the actual type precisely.
129 //
130 // 1. Class is written directly in the message:
131 // \code
132 // [ActualClass classMethod];
133 // \endcode
134 if (MessageExpr->getReceiverKind() == ObjCMessageExpr::Class) {
135 return {.Type: MessageExpr->getClassReceiver()->getAs<ObjCObjectType>(),
136 /*Precise=*/true};
137 }
138
139 // 2. Receiver is 'super' from a class method (a.k.a 'super' is a
140 // class object).
141 // \code
142 // [super classMethod];
143 // \endcode
144 if (MessageExpr->getReceiverKind() == ObjCMessageExpr::SuperClass) {
145 return {.Type: MessageExpr->getSuperType()->getAs<ObjCObjectType>(),
146 /*Precise=*/true};
147 }
148
149 // 3. Receiver is 'super' from an instance method (a.k.a 'super' is an
150 // instance of a super class).
151 // \code
152 // [super instanceMethod];
153 // \encode
154 if (MessageExpr->getReceiverKind() == ObjCMessageExpr::SuperInstance) {
155 if (const auto *ObjTy =
156 MessageExpr->getSuperType()->getAs<ObjCObjectPointerType>())
157 return {.Type: ObjTy->getObjectType(), /*Precise=*/true};
158 }
159
160 const Expr *RecE = MessageExpr->getInstanceReceiver();
161
162 if (!RecE)
163 return {};
164
165 // Otherwise, let's try to get type information from our estimations of
166 // runtime types.
167 QualType InferredType;
168 SVal ReceiverSVal = C.getSVal(S: RecE);
169 ProgramStateRef State = C.getState();
170
171 if (const MemRegion *ReceiverRegion = ReceiverSVal.getAsRegion()) {
172 if (DynamicTypeInfo DTI = getDynamicTypeInfo(State, MR: ReceiverRegion)) {
173 InferredType = DTI.getType().getCanonicalType();
174 }
175 }
176
177 if (SymbolRef ReceiverSymbol = ReceiverSVal.getAsSymbol()) {
178 if (InferredType.isNull()) {
179 InferredType = ReceiverSymbol->getType();
180 }
181
182 // If receiver is a Class object, we want to figure out the type it
183 // represents.
184 if (isObjCClassType(Type: InferredType)) {
185 // We actually might have some info on what type is contained in there.
186 if (DynamicTypeInfo DTI =
187 getClassObjectDynamicTypeInfo(State, Sym: ReceiverSymbol)) {
188
189 // Types in Class objects can be ONLY Objective-C types
190 return {.Type: cast<ObjCObjectType>(Val: DTI.getType()), .Precise: !DTI.canBeASubClass()};
191 }
192
193 SVal SelfSVal = State->getSelfSVal(LC: C.getLocationContext());
194
195 // Another way we can guess what is in Class object, is when it is a
196 // 'self' variable of the current class method.
197 if (ReceiverSVal == SelfSVal) {
198 // In this case, we should return the type of the enclosing class
199 // declaration.
200 if (const ObjCMethodDecl *MD =
201 dyn_cast<ObjCMethodDecl>(Val: C.getStackFrame()->getDecl()))
202 if (const ObjCObjectType *ObjTy = dyn_cast<ObjCObjectType>(
203 Val: MD->getClassInterface()->getTypeForDecl()))
204 return {.Type: ObjTy};
205 }
206 }
207 }
208
209 // Unfortunately, it seems like we have no idea what that type is.
210 if (InferredType.isNull()) {
211 return {};
212 }
213
214 // We can end up here if we got some dynamic type info and the
215 // receiver is not one of the known Class objects.
216 if (const auto *ReceiverInferredType =
217 dyn_cast<ObjCObjectPointerType>(Val&: InferredType)) {
218 return {.Type: ReceiverInferredType->getObjectType()};
219 }
220
221 // Any other type (like 'Class') is not really useful at this point.
222 return {};
223}
224} // end anonymous namespace
225
226void DynamicTypePropagation::checkDeadSymbols(SymbolReaper &SR,
227 CheckerContext &C) const {
228 ProgramStateRef State = removeDeadTypes(State: C.getState(), SR);
229 State = removeDeadClassObjectTypes(State, SR);
230
231 MostSpecializedTypeArgsMapTy TyArgMap =
232 State->get<MostSpecializedTypeArgsMap>();
233 for (SymbolRef Sym : llvm::make_first_range(c&: TyArgMap)) {
234 if (SR.isDead(sym: Sym)) {
235 State = State->remove<MostSpecializedTypeArgsMap>(K: Sym);
236 }
237 }
238
239 C.addTransition(State);
240}
241
242static void recordFixedType(const MemRegion *Region, const CXXMethodDecl *MD,
243 CheckerContext &C) {
244 assert(Region);
245 assert(MD);
246
247 ASTContext &Ctx = C.getASTContext();
248 QualType Ty = Ctx.getPointerType(T: Ctx.getRecordType(Decl: MD->getParent()));
249
250 ProgramStateRef State = C.getState();
251 State = setDynamicTypeInfo(State, MR: Region, NewTy: Ty, /*CanBeSubClassed=*/false);
252 C.addTransition(State);
253}
254
255void DynamicTypePropagation::checkPreCall(const CallEvent &Call,
256 CheckerContext &C) const {
257 if (const CXXConstructorCall *Ctor = dyn_cast<CXXConstructorCall>(Val: &Call)) {
258 // C++11 [class.cdtor]p4: When a virtual function is called directly or
259 // indirectly from a constructor or from a destructor, including during
260 // the construction or destruction of the class's non-static data members,
261 // and the object to which the call applies is the object under
262 // construction or destruction, the function called is the final overrider
263 // in the constructor's or destructor's class and not one overriding it in
264 // a more-derived class.
265
266 switch (Ctor->getOriginExpr()->getConstructionKind()) {
267 case CXXConstructionKind::Complete:
268 case CXXConstructionKind::Delegating:
269 // No additional type info necessary.
270 return;
271 case CXXConstructionKind::NonVirtualBase:
272 case CXXConstructionKind::VirtualBase:
273 if (const MemRegion *Target = Ctor->getCXXThisVal().getAsRegion())
274 recordFixedType(Region: Target, MD: Ctor->getDecl(), C);
275 return;
276 }
277
278 return;
279 }
280
281 if (const CXXDestructorCall *Dtor = dyn_cast<CXXDestructorCall>(Val: &Call)) {
282 // C++11 [class.cdtor]p4 (see above)
283 if (!Dtor->isBaseDestructor())
284 return;
285
286 const MemRegion *Target = Dtor->getCXXThisVal().getAsRegion();
287 if (!Target)
288 return;
289
290 const Decl *D = Dtor->getDecl();
291 if (!D)
292 return;
293
294 recordFixedType(Region: Target, MD: cast<CXXDestructorDecl>(Val: D), C);
295 return;
296 }
297}
298
299void DynamicTypePropagation::checkPostCall(const CallEvent &Call,
300 CheckerContext &C) const {
301 // We can obtain perfect type info for return values from some calls.
302 if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(Val: &Call)) {
303
304 // Get the returned value if it's a region.
305 const MemRegion *RetReg = Call.getReturnValue().getAsRegion();
306 if (!RetReg)
307 return;
308
309 ProgramStateRef State = C.getState();
310 const ObjCMethodDecl *D = Msg->getDecl();
311
312 if (D && D->hasRelatedResultType()) {
313 switch (Msg->getMethodFamily()) {
314 default:
315 break;
316
317 // We assume that the type of the object returned by alloc and new are the
318 // pointer to the object of the class specified in the receiver of the
319 // message.
320 case OMF_alloc:
321 case OMF_new: {
322 // Get the type of object that will get created.
323 RuntimeType ObjTy = inferReceiverType(Message: *Msg, C);
324
325 if (!ObjTy)
326 return;
327
328 QualType DynResTy =
329 C.getASTContext().getObjCObjectPointerType(OIT: QualType(ObjTy.Type, 0));
330 // We used to assume that whatever type we got from inferring the
331 // type is actually precise (and it is not exactly correct).
332 // A big portion of the existing behavior depends on that assumption
333 // (e.g. certain inlining won't take place). For this reason, we don't
334 // use ObjTy.Precise flag here.
335 //
336 // TODO: We should mitigate this problem some time in the future
337 // and replace hardcoded 'false' with '!ObjTy.Precise'.
338 C.addTransition(State: setDynamicTypeInfo(State, MR: RetReg, NewTy: DynResTy, CanBeSubClassed: false));
339 break;
340 }
341 case OMF_init: {
342 // Assume, the result of the init method has the same dynamic type as
343 // the receiver and propagate the dynamic type info.
344 const MemRegion *RecReg = Msg->getReceiverSVal().getAsRegion();
345 if (!RecReg)
346 return;
347 DynamicTypeInfo RecDynType = getDynamicTypeInfo(State, MR: RecReg);
348 C.addTransition(State: setDynamicTypeInfo(State, MR: RetReg, NewTy: RecDynType));
349 break;
350 }
351 }
352 }
353 return;
354 }
355
356 if (const CXXConstructorCall *Ctor = dyn_cast<CXXConstructorCall>(Val: &Call)) {
357 // We may need to undo the effects of our pre-call check.
358 switch (Ctor->getOriginExpr()->getConstructionKind()) {
359 case CXXConstructionKind::Complete:
360 case CXXConstructionKind::Delegating:
361 // No additional work necessary.
362 // Note: This will leave behind the actual type of the object for
363 // complete constructors, but arguably that's a good thing, since it
364 // means the dynamic type info will be correct even for objects
365 // constructed with operator new.
366 return;
367 case CXXConstructionKind::NonVirtualBase:
368 case CXXConstructionKind::VirtualBase:
369 if (const MemRegion *Target = Ctor->getCXXThisVal().getAsRegion()) {
370 // We just finished a base constructor. Now we can use the subclass's
371 // type when resolving virtual calls.
372 const LocationContext *LCtx = C.getLocationContext();
373
374 // FIXME: In C++17 classes with non-virtual bases may be treated as
375 // aggregates, and in such case no top-frame constructor will be called.
376 // Figure out if we need to do anything in this case.
377 // FIXME: Instead of relying on the ParentMap, we should have the
378 // trigger-statement (InitListExpr or CXXParenListInitExpr in this case)
379 // available in this callback, ideally as part of CallEvent.
380 if (isa_and_nonnull<InitListExpr, CXXParenListInitExpr>(
381 Val: LCtx->getParentMap().getParent(S: Ctor->getOriginExpr())))
382 return;
383
384 recordFixedType(Region: Target, MD: cast<CXXConstructorDecl>(Val: LCtx->getDecl()), C);
385 }
386 return;
387 }
388 }
389}
390
391/// TODO: Handle explicit casts.
392/// Handle C++ casts.
393///
394/// Precondition: the cast is between ObjCObjectPointers.
395ExplodedNode *DynamicTypePropagation::dynamicTypePropagationOnCasts(
396 const CastExpr *CE, ProgramStateRef &State, CheckerContext &C) const {
397 // We only track type info for regions.
398 const MemRegion *ToR = C.getSVal(S: CE).getAsRegion();
399 if (!ToR)
400 return C.getPredecessor();
401
402 if (isa<ExplicitCastExpr>(Val: CE))
403 return C.getPredecessor();
404
405 if (const Type *NewTy = getBetterObjCType(CastE: CE, C)) {
406 State = setDynamicTypeInfo(State, MR: ToR, NewTy: QualType(NewTy, 0));
407 return C.addTransition(State);
408 }
409 return C.getPredecessor();
410}
411
412void DynamicTypePropagation::checkPostStmt(const CXXNewExpr *NewE,
413 CheckerContext &C) const {
414 if (NewE->isArray())
415 return;
416
417 // We only track dynamic type info for regions.
418 const MemRegion *MR = C.getSVal(S: NewE).getAsRegion();
419 if (!MR)
420 return;
421
422 C.addTransition(State: setDynamicTypeInfo(State: C.getState(), MR, NewTy: NewE->getType(),
423 /*CanBeSubClassed=*/false));
424}
425
426// Return a better dynamic type if one can be derived from the cast.
427// Compare the current dynamic type of the region and the new type to which we
428// are casting. If the new type is lower in the inheritance hierarchy, pick it.
429const ObjCObjectPointerType *
430DynamicTypePropagation::getBetterObjCType(const Expr *CastE,
431 CheckerContext &C) const {
432 const MemRegion *ToR = C.getSVal(S: CastE).getAsRegion();
433 assert(ToR);
434
435 // Get the old and new types.
436 const ObjCObjectPointerType *NewTy =
437 CastE->getType()->getAs<ObjCObjectPointerType>();
438 if (!NewTy)
439 return nullptr;
440 QualType OldDTy = getDynamicTypeInfo(State: C.getState(), MR: ToR).getType();
441 if (OldDTy.isNull()) {
442 return NewTy;
443 }
444 const ObjCObjectPointerType *OldTy =
445 OldDTy->getAs<ObjCObjectPointerType>();
446 if (!OldTy)
447 return nullptr;
448
449 // Id the old type is 'id', the new one is more precise.
450 if (OldTy->isObjCIdType() && !NewTy->isObjCIdType())
451 return NewTy;
452
453 // Return new if it's a subclass of old.
454 const ObjCInterfaceDecl *ToI = NewTy->getInterfaceDecl();
455 const ObjCInterfaceDecl *FromI = OldTy->getInterfaceDecl();
456 if (ToI && FromI && FromI->isSuperClassOf(I: ToI))
457 return NewTy;
458
459 return nullptr;
460}
461
462static const ObjCObjectPointerType *getMostInformativeDerivedClassImpl(
463 const ObjCObjectPointerType *From, const ObjCObjectPointerType *To,
464 const ObjCObjectPointerType *MostInformativeCandidate, ASTContext &C) {
465 // Checking if from and to are the same classes modulo specialization.
466 if (From->getInterfaceDecl()->getCanonicalDecl() ==
467 To->getInterfaceDecl()->getCanonicalDecl()) {
468 if (To->isSpecialized()) {
469 assert(MostInformativeCandidate->isSpecialized());
470 return MostInformativeCandidate;
471 }
472 return From;
473 }
474
475 if (To->getObjectType()->getSuperClassType().isNull()) {
476 // If To has no super class and From and To aren't the same then
477 // To was not actually a descendent of From. In this case the best we can
478 // do is 'From'.
479 return From;
480 }
481
482 const auto *SuperOfTo =
483 To->getObjectType()->getSuperClassType()->castAs<ObjCObjectType>();
484 assert(SuperOfTo);
485 QualType SuperPtrOfToQual =
486 C.getObjCObjectPointerType(OIT: QualType(SuperOfTo, 0));
487 const auto *SuperPtrOfTo = SuperPtrOfToQual->castAs<ObjCObjectPointerType>();
488 if (To->isUnspecialized())
489 return getMostInformativeDerivedClassImpl(From, To: SuperPtrOfTo, MostInformativeCandidate: SuperPtrOfTo,
490 C);
491 else
492 return getMostInformativeDerivedClassImpl(From, To: SuperPtrOfTo,
493 MostInformativeCandidate, C);
494}
495
496/// A downcast may loose specialization information. E. g.:
497/// MutableMap<T, U> : Map
498/// The downcast to MutableMap looses the information about the types of the
499/// Map (due to the type parameters are not being forwarded to Map), and in
500/// general there is no way to recover that information from the
501/// declaration. In order to have to most information, lets find the most
502/// derived type that has all the type parameters forwarded.
503///
504/// Get the a subclass of \p From (which has a lower bound \p To) that do not
505/// loose information about type parameters. \p To has to be a subclass of
506/// \p From. From has to be specialized.
507static const ObjCObjectPointerType *
508getMostInformativeDerivedClass(const ObjCObjectPointerType *From,
509 const ObjCObjectPointerType *To, ASTContext &C) {
510 return getMostInformativeDerivedClassImpl(From, To, MostInformativeCandidate: To, C);
511}
512
513/// Inputs:
514/// \param StaticLowerBound Static lower bound for a symbol. The dynamic lower
515/// bound might be the subclass of this type.
516/// \param StaticUpperBound A static upper bound for a symbol.
517/// \p StaticLowerBound expected to be the subclass of \p StaticUpperBound.
518/// \param Current The type that was inferred for a symbol in a previous
519/// context. Might be null when this is the first time that inference happens.
520/// Precondition:
521/// \p StaticLowerBound or \p StaticUpperBound is specialized. If \p Current
522/// is not null, it is specialized.
523/// Possible cases:
524/// (1) The \p Current is null and \p StaticLowerBound <: \p StaticUpperBound
525/// (2) \p StaticLowerBound <: \p Current <: \p StaticUpperBound
526/// (3) \p Current <: \p StaticLowerBound <: \p StaticUpperBound
527/// (4) \p StaticLowerBound <: \p StaticUpperBound <: \p Current
528/// Effect:
529/// Use getMostInformativeDerivedClass with the upper and lower bound of the
530/// set {\p StaticLowerBound, \p Current, \p StaticUpperBound}. The computed
531/// lower bound must be specialized. If the result differs from \p Current or
532/// \p Current is null, store the result.
533static bool
534storeWhenMoreInformative(ProgramStateRef &State, SymbolRef Sym,
535 const ObjCObjectPointerType *const *Current,
536 const ObjCObjectPointerType *StaticLowerBound,
537 const ObjCObjectPointerType *StaticUpperBound,
538 ASTContext &C) {
539 // TODO: The above 4 cases are not exhaustive. In particular, it is possible
540 // for Current to be incomparable with StaticLowerBound, StaticUpperBound,
541 // or both.
542 //
543 // For example, suppose Foo<T> and Bar<T> are unrelated types.
544 //
545 // Foo<T> *f = ...
546 // Bar<T> *b = ...
547 //
548 // id t1 = b;
549 // f = t1;
550 // id t2 = f; // StaticLowerBound is Foo<T>, Current is Bar<T>
551 //
552 // We should either constrain the callers of this function so that the stated
553 // preconditions hold (and assert it) or rewrite the function to expicitly
554 // handle the additional cases.
555
556 // Precondition
557 assert(StaticUpperBound->isSpecialized() ||
558 StaticLowerBound->isSpecialized());
559 assert(!Current || (*Current)->isSpecialized());
560
561 // Case (1)
562 if (!Current) {
563 if (StaticUpperBound->isUnspecialized()) {
564 State = State->set<MostSpecializedTypeArgsMap>(K: Sym, E: StaticLowerBound);
565 return true;
566 }
567 // Upper bound is specialized.
568 const ObjCObjectPointerType *WithMostInfo =
569 getMostInformativeDerivedClass(From: StaticUpperBound, To: StaticLowerBound, C);
570 State = State->set<MostSpecializedTypeArgsMap>(K: Sym, E: WithMostInfo);
571 return true;
572 }
573
574 // Case (3)
575 if (C.canAssignObjCInterfaces(LHSOPT: StaticLowerBound, RHSOPT: *Current)) {
576 return false;
577 }
578
579 // Case (4)
580 if (C.canAssignObjCInterfaces(LHSOPT: *Current, RHSOPT: StaticUpperBound)) {
581 // The type arguments might not be forwarded at any point of inheritance.
582 const ObjCObjectPointerType *WithMostInfo =
583 getMostInformativeDerivedClass(From: *Current, To: StaticUpperBound, C);
584 WithMostInfo =
585 getMostInformativeDerivedClass(From: WithMostInfo, To: StaticLowerBound, C);
586 if (WithMostInfo == *Current)
587 return false;
588 State = State->set<MostSpecializedTypeArgsMap>(K: Sym, E: WithMostInfo);
589 return true;
590 }
591
592 // Case (2)
593 const ObjCObjectPointerType *WithMostInfo =
594 getMostInformativeDerivedClass(From: *Current, To: StaticLowerBound, C);
595 if (WithMostInfo != *Current) {
596 State = State->set<MostSpecializedTypeArgsMap>(K: Sym, E: WithMostInfo);
597 return true;
598 }
599
600 return false;
601}
602
603/// Type inference based on static type information that is available for the
604/// cast and the tracked type information for the given symbol. When the tracked
605/// symbol and the destination type of the cast are unrelated, report an error.
606void DynamicTypePropagation::checkPostStmt(const CastExpr *CE,
607 CheckerContext &C) const {
608 if (CE->getCastKind() != CK_BitCast)
609 return;
610
611 QualType OriginType = CE->getSubExpr()->getType();
612 QualType DestType = CE->getType();
613
614 const auto *OrigObjectPtrType = OriginType->getAs<ObjCObjectPointerType>();
615 const auto *DestObjectPtrType = DestType->getAs<ObjCObjectPointerType>();
616
617 if (!OrigObjectPtrType || !DestObjectPtrType)
618 return;
619
620 ProgramStateRef State = C.getState();
621 ExplodedNode *AfterTypeProp = dynamicTypePropagationOnCasts(CE, State, C);
622
623 ASTContext &ASTCtxt = C.getASTContext();
624
625 // This checker detects the subtyping relationships using the assignment
626 // rules. In order to be able to do this the kindofness must be stripped
627 // first. The checker treats every type as kindof type anyways: when the
628 // tracked type is the subtype of the static type it tries to look up the
629 // methods in the tracked type first.
630 OrigObjectPtrType = OrigObjectPtrType->stripObjCKindOfTypeAndQuals(ctx: ASTCtxt);
631 DestObjectPtrType = DestObjectPtrType->stripObjCKindOfTypeAndQuals(ctx: ASTCtxt);
632
633 if (OrigObjectPtrType->isUnspecialized() &&
634 DestObjectPtrType->isUnspecialized())
635 return;
636
637 SymbolRef Sym = C.getSVal(S: CE).getAsSymbol();
638 if (!Sym)
639 return;
640
641 const ObjCObjectPointerType *const *TrackedType =
642 State->get<MostSpecializedTypeArgsMap>(key: Sym);
643
644 if (isa<ExplicitCastExpr>(Val: CE)) {
645 // Treat explicit casts as an indication from the programmer that the
646 // Objective-C type system is not rich enough to express the needed
647 // invariant. In such cases, forget any existing information inferred
648 // about the type arguments. We don't assume the casted-to specialized
649 // type here because the invariant the programmer specifies in the cast
650 // may only hold at this particular program point and not later ones.
651 // We don't want a suppressing cast to require a cascade of casts down the
652 // line.
653 if (TrackedType) {
654 State = State->remove<MostSpecializedTypeArgsMap>(K: Sym);
655 C.addTransition(State, Pred: AfterTypeProp);
656 }
657 return;
658 }
659
660 // Check which assignments are legal.
661 bool OrigToDest =
662 ASTCtxt.canAssignObjCInterfaces(LHSOPT: DestObjectPtrType, RHSOPT: OrigObjectPtrType);
663 bool DestToOrig =
664 ASTCtxt.canAssignObjCInterfaces(LHSOPT: OrigObjectPtrType, RHSOPT: DestObjectPtrType);
665
666 // The tracked type should be the sub or super class of the static destination
667 // type. When an (implicit) upcast or a downcast happens according to static
668 // types, and there is no subtyping relationship between the tracked and the
669 // static destination types, it indicates an error.
670 if (TrackedType &&
671 !ASTCtxt.canAssignObjCInterfaces(LHSOPT: DestObjectPtrType, RHSOPT: *TrackedType) &&
672 !ASTCtxt.canAssignObjCInterfaces(LHSOPT: *TrackedType, RHSOPT: DestObjectPtrType)) {
673 // This distinct program point tag is needed because `State` can be
674 // identical to the state of the node `AfterTypeProp`, and in that case
675 // `generateNonFatalErrorNode` would "cache out" and return nullptr
676 // (instead of re-creating an already existing node).
677 static SimpleProgramPointTag IllegalConv("DynamicTypePropagation",
678 "IllegalConversion");
679 ExplodedNode *N =
680 C.generateNonFatalErrorNode(State, Pred: AfterTypeProp, Tag: &IllegalConv);
681 if (N)
682 reportGenericsBug(From: *TrackedType, To: DestObjectPtrType, N, Sym, C);
683 return;
684 }
685
686 // Handle downcasts and upcasts.
687
688 const ObjCObjectPointerType *LowerBound = DestObjectPtrType;
689 const ObjCObjectPointerType *UpperBound = OrigObjectPtrType;
690 if (OrigToDest && !DestToOrig)
691 std::swap(a&: LowerBound, b&: UpperBound);
692
693 // The id type is not a real bound. Eliminate it.
694 LowerBound = LowerBound->isObjCIdType() ? UpperBound : LowerBound;
695 UpperBound = UpperBound->isObjCIdType() ? LowerBound : UpperBound;
696
697 if (storeWhenMoreInformative(State, Sym, Current: TrackedType, StaticLowerBound: LowerBound, StaticUpperBound: UpperBound,
698 C&: ASTCtxt)) {
699 C.addTransition(State, Pred: AfterTypeProp);
700 }
701}
702
703static const Expr *stripCastsAndSugar(const Expr *E) {
704 E = E->IgnoreParenImpCasts();
705 if (const PseudoObjectExpr *POE = dyn_cast<PseudoObjectExpr>(Val: E))
706 E = POE->getSyntacticForm()->IgnoreParenImpCasts();
707 if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Val: E))
708 E = OVE->getSourceExpr()->IgnoreParenImpCasts();
709 return E;
710}
711
712static bool isObjCTypeParamDependent(QualType Type) {
713 // It is illegal to typedef parameterized types inside an interface. Therefore
714 // an Objective-C type can only be dependent on a type parameter when the type
715 // parameter structurally present in the type itself.
716 class IsObjCTypeParamDependentTypeVisitor
717 : public DynamicRecursiveASTVisitor {
718 public:
719 IsObjCTypeParamDependentTypeVisitor() = default;
720 bool VisitObjCTypeParamType(ObjCTypeParamType *Type) override {
721 if (isa<ObjCTypeParamDecl>(Val: Type->getDecl())) {
722 Result = true;
723 return false;
724 }
725 return true;
726 }
727
728 bool Result = false;
729 };
730
731 IsObjCTypeParamDependentTypeVisitor Visitor;
732 Visitor.TraverseType(T: Type);
733 return Visitor.Result;
734}
735
736/// A method might not be available in the interface indicated by the static
737/// type. However it might be available in the tracked type. In order to
738/// properly substitute the type parameters we need the declaration context of
739/// the method. The more specialized the enclosing class of the method is, the
740/// more likely that the parameter substitution will be successful.
741static const ObjCMethodDecl *
742findMethodDecl(const ObjCMessageExpr *MessageExpr,
743 const ObjCObjectPointerType *TrackedType, ASTContext &ASTCtxt) {
744 const ObjCMethodDecl *Method = nullptr;
745
746 QualType ReceiverType = MessageExpr->getReceiverType();
747
748 // Do this "devirtualization" on instance and class methods only. Trust the
749 // static type on super and super class calls.
750 if (MessageExpr->getReceiverKind() == ObjCMessageExpr::Instance ||
751 MessageExpr->getReceiverKind() == ObjCMessageExpr::Class) {
752 // When the receiver type is id, Class, or some super class of the tracked
753 // type, look up the method in the tracked type, not in the receiver type.
754 // This way we preserve more information.
755 if (ReceiverType->isObjCIdType() || ReceiverType->isObjCClassType() ||
756 ASTCtxt.canAssignObjCInterfaces(
757 LHSOPT: ReceiverType->castAs<ObjCObjectPointerType>(), RHSOPT: TrackedType)) {
758 const ObjCInterfaceDecl *InterfaceDecl = TrackedType->getInterfaceDecl();
759 // The method might not be found.
760 Selector Sel = MessageExpr->getSelector();
761 Method = InterfaceDecl->lookupInstanceMethod(Sel);
762 if (!Method)
763 Method = InterfaceDecl->lookupClassMethod(Sel);
764 }
765 }
766
767 // Fallback to statick method lookup when the one based on the tracked type
768 // failed.
769 return Method ? Method : MessageExpr->getMethodDecl();
770}
771
772/// Get the returned ObjCObjectPointerType by a method based on the tracked type
773/// information, or null pointer when the returned type is not an
774/// ObjCObjectPointerType.
775static QualType getReturnTypeForMethod(
776 const ObjCMethodDecl *Method, ArrayRef<QualType> TypeArgs,
777 const ObjCObjectPointerType *SelfType, ASTContext &C) {
778 QualType StaticResultType = Method->getReturnType();
779
780 // Is the return type declared as instance type?
781 if (StaticResultType == C.getObjCInstanceType())
782 return QualType(SelfType, 0);
783
784 // Check whether the result type depends on a type parameter.
785 if (!isObjCTypeParamDependent(Type: StaticResultType))
786 return QualType();
787
788 QualType ResultType = StaticResultType.substObjCTypeArgs(
789 ctx&: C, typeArgs: TypeArgs, context: ObjCSubstitutionContext::Result);
790
791 return ResultType;
792}
793
794/// When the receiver has a tracked type, use that type to validate the
795/// argumments of the message expression and the return value.
796void DynamicTypePropagation::checkPreObjCMessage(const ObjCMethodCall &M,
797 CheckerContext &C) const {
798 ProgramStateRef State = C.getState();
799 SymbolRef Sym = M.getReceiverSVal().getAsSymbol();
800 if (!Sym)
801 return;
802
803 const ObjCObjectPointerType *const *TrackedType =
804 State->get<MostSpecializedTypeArgsMap>(key: Sym);
805 if (!TrackedType)
806 return;
807
808 // Get the type arguments from tracked type and substitute type arguments
809 // before do the semantic check.
810
811 ASTContext &ASTCtxt = C.getASTContext();
812 const ObjCMessageExpr *MessageExpr = M.getOriginExpr();
813 const ObjCMethodDecl *Method =
814 findMethodDecl(MessageExpr, TrackedType: *TrackedType, ASTCtxt);
815
816 // It is possible to call non-existent methods in Obj-C.
817 if (!Method)
818 return;
819
820 // If the method is declared on a class that has a non-invariant
821 // type parameter, don't warn about parameter mismatches after performing
822 // substitution. This prevents warning when the programmer has purposely
823 // casted the receiver to a super type or unspecialized type but the analyzer
824 // has a more precise tracked type than the programmer intends at the call
825 // site.
826 //
827 // For example, consider NSArray (which has a covariant type parameter)
828 // and NSMutableArray (a subclass of NSArray where the type parameter is
829 // invariant):
830 // NSMutableArray *a = [[NSMutableArray<NSString *> alloc] init;
831 //
832 // [a containsObject:number]; // Safe: -containsObject is defined on NSArray.
833 // NSArray<NSObject *> *other = [a arrayByAddingObject:number] // Safe
834 //
835 // [a addObject:number] // Unsafe: -addObject: is defined on NSMutableArray
836 //
837
838 const ObjCInterfaceDecl *Interface = Method->getClassInterface();
839 if (!Interface)
840 return;
841
842 ObjCTypeParamList *TypeParams = Interface->getTypeParamList();
843 if (!TypeParams)
844 return;
845
846 for (ObjCTypeParamDecl *TypeParam : *TypeParams) {
847 if (TypeParam->getVariance() != ObjCTypeParamVariance::Invariant)
848 return;
849 }
850
851 std::optional<ArrayRef<QualType>> TypeArgs =
852 (*TrackedType)->getObjCSubstitutions(dc: Method->getDeclContext());
853 // This case might happen when there is an unspecialized override of a
854 // specialized method.
855 if (!TypeArgs)
856 return;
857
858 for (unsigned i = 0; i < Method->param_size(); i++) {
859 const Expr *Arg = MessageExpr->getArg(Arg: i);
860 const ParmVarDecl *Param = Method->parameters()[i];
861
862 QualType OrigParamType = Param->getType();
863 if (!isObjCTypeParamDependent(Type: OrigParamType))
864 continue;
865
866 QualType ParamType = OrigParamType.substObjCTypeArgs(
867 ctx&: ASTCtxt, typeArgs: *TypeArgs, context: ObjCSubstitutionContext::Parameter);
868 // Check if it can be assigned
869 const auto *ParamObjectPtrType = ParamType->getAs<ObjCObjectPointerType>();
870 const auto *ArgObjectPtrType =
871 stripCastsAndSugar(E: Arg)->getType()->getAs<ObjCObjectPointerType>();
872 if (!ParamObjectPtrType || !ArgObjectPtrType)
873 continue;
874
875 // Check if we have more concrete tracked type that is not a super type of
876 // the static argument type.
877 SVal ArgSVal = M.getArgSVal(Index: i);
878 SymbolRef ArgSym = ArgSVal.getAsSymbol();
879 if (ArgSym) {
880 const ObjCObjectPointerType *const *TrackedArgType =
881 State->get<MostSpecializedTypeArgsMap>(key: ArgSym);
882 if (TrackedArgType &&
883 ASTCtxt.canAssignObjCInterfaces(LHSOPT: ArgObjectPtrType, RHSOPT: *TrackedArgType)) {
884 ArgObjectPtrType = *TrackedArgType;
885 }
886 }
887
888 // Warn when argument is incompatible with the parameter.
889 if (!ASTCtxt.canAssignObjCInterfaces(LHSOPT: ParamObjectPtrType,
890 RHSOPT: ArgObjectPtrType)) {
891 ExplodedNode *N = C.generateNonFatalErrorNode(State);
892 reportGenericsBug(From: ArgObjectPtrType, To: ParamObjectPtrType, N, Sym, C, ReportedNode: Arg);
893 return;
894 }
895 }
896}
897
898/// This callback is used to infer the types for Class variables. This info is
899/// used later to validate messages that sent to classes. Class variables are
900/// initialized with by invoking the 'class' method on a class.
901/// This method is also used to infer the type information for the return
902/// types.
903// TODO: right now it only tracks generic types. Extend this to track every
904// type in the DynamicTypeMap and diagnose type errors!
905void DynamicTypePropagation::checkPostObjCMessage(const ObjCMethodCall &M,
906 CheckerContext &C) const {
907 const ObjCMessageExpr *MessageExpr = M.getOriginExpr();
908
909 SymbolRef RetSym = M.getReturnValue().getAsSymbol();
910 if (!RetSym)
911 return;
912
913 Selector Sel = MessageExpr->getSelector();
914 ProgramStateRef State = C.getState();
915
916 // Here we try to propagate information on Class objects.
917 if (Sel.getAsString() == "class") {
918 // We try to figure out the type from the receiver of the 'class' message.
919 if (RuntimeType ReceiverRuntimeType = inferReceiverType(Message: M, C)) {
920
921 ReceiverRuntimeType.Type->getSuperClassType();
922 QualType ReceiverClassType(ReceiverRuntimeType.Type, 0);
923
924 // We want to consider only precise information on generics.
925 if (ReceiverRuntimeType.Type->isSpecialized() &&
926 ReceiverRuntimeType.Precise) {
927 QualType ReceiverClassPointerType =
928 C.getASTContext().getObjCObjectPointerType(OIT: ReceiverClassType);
929 const auto *InferredType =
930 ReceiverClassPointerType->castAs<ObjCObjectPointerType>();
931 State = State->set<MostSpecializedTypeArgsMap>(K: RetSym, E: InferredType);
932 }
933
934 // Constrain the resulting class object to the inferred type.
935 State = setClassObjectDynamicTypeInfo(State, Sym: RetSym, NewTy: ReceiverClassType,
936 CanBeSubClassed: !ReceiverRuntimeType.Precise);
937
938 C.addTransition(State);
939 return;
940 }
941 }
942
943 if (Sel.getAsString() == "superclass") {
944 // We try to figure out the type from the receiver of the 'superclass'
945 // message.
946 if (RuntimeType ReceiverRuntimeType = inferReceiverType(Message: M, C)) {
947
948 // Result type would be a super class of the receiver's type.
949 QualType ReceiversSuperClass =
950 ReceiverRuntimeType.Type->getSuperClassType();
951
952 // Check if it really had super class.
953 //
954 // TODO: we can probably pay closer attention to cases when the class
955 // object can be 'nil' as the result of such message.
956 if (!ReceiversSuperClass.isNull()) {
957 // Constrain the resulting class object to the inferred type.
958 State = setClassObjectDynamicTypeInfo(
959 State, Sym: RetSym, NewTy: ReceiversSuperClass, CanBeSubClassed: !ReceiverRuntimeType.Precise);
960
961 C.addTransition(State);
962 }
963 return;
964 }
965 }
966
967 // Tracking for return types.
968 SymbolRef RecSym = M.getReceiverSVal().getAsSymbol();
969 if (!RecSym)
970 return;
971
972 const ObjCObjectPointerType *const *TrackedType =
973 State->get<MostSpecializedTypeArgsMap>(key: RecSym);
974 if (!TrackedType)
975 return;
976
977 ASTContext &ASTCtxt = C.getASTContext();
978 const ObjCMethodDecl *Method =
979 findMethodDecl(MessageExpr, TrackedType: *TrackedType, ASTCtxt);
980 if (!Method)
981 return;
982
983 std::optional<ArrayRef<QualType>> TypeArgs =
984 (*TrackedType)->getObjCSubstitutions(dc: Method->getDeclContext());
985 if (!TypeArgs)
986 return;
987
988 QualType ResultType =
989 getReturnTypeForMethod(Method, TypeArgs: *TypeArgs, SelfType: *TrackedType, C&: ASTCtxt);
990 // The static type is the same as the deduced type.
991 if (ResultType.isNull())
992 return;
993
994 const MemRegion *RetRegion = M.getReturnValue().getAsRegion();
995 ExplodedNode *Pred = C.getPredecessor();
996 // When there is an entry available for the return symbol in DynamicTypeMap,
997 // the call was inlined, and the information in the DynamicTypeMap is should
998 // be precise.
999 if (RetRegion && !getRawDynamicTypeInfo(State, MR: RetRegion)) {
1000 // TODO: we have duplicated information in DynamicTypeMap and
1001 // MostSpecializedTypeArgsMap. We should only store anything in the later if
1002 // the stored data differs from the one stored in the former.
1003 State = setDynamicTypeInfo(State, MR: RetRegion, NewTy: ResultType,
1004 /*CanBeSubClassed=*/true);
1005 Pred = C.addTransition(State);
1006 }
1007
1008 const auto *ResultPtrType = ResultType->getAs<ObjCObjectPointerType>();
1009
1010 if (!ResultPtrType || ResultPtrType->isUnspecialized())
1011 return;
1012
1013 // When the result is a specialized type and it is not tracked yet, track it
1014 // for the result symbol.
1015 if (!State->get<MostSpecializedTypeArgsMap>(key: RetSym)) {
1016 State = State->set<MostSpecializedTypeArgsMap>(K: RetSym, E: ResultPtrType);
1017 C.addTransition(State, Pred);
1018 }
1019}
1020
1021void DynamicTypePropagation::reportGenericsBug(
1022 const ObjCObjectPointerType *From, const ObjCObjectPointerType *To,
1023 ExplodedNode *N, SymbolRef Sym, CheckerContext &C,
1024 const Stmt *ReportedNode) const {
1025 if (!ObjCGenericsChecker.isEnabled())
1026 return;
1027
1028 SmallString<192> Buf;
1029 llvm::raw_svector_ostream OS(Buf);
1030 OS << "Conversion from value of type '";
1031 QualType::print(ty: From, qs: Qualifiers(), OS, policy: C.getLangOpts(), PlaceHolder: llvm::Twine());
1032 OS << "' to incompatible type '";
1033 QualType::print(ty: To, qs: Qualifiers(), OS, policy: C.getLangOpts(), PlaceHolder: llvm::Twine());
1034 OS << "'";
1035 auto R = std::make_unique<PathSensitiveBugReport>(args: ObjCGenericsChecker,
1036 args: OS.str(), args&: N);
1037 R->markInteresting(sym: Sym);
1038 R->addVisitor(visitor: std::make_unique<GenericsBugVisitor>(args&: Sym));
1039 if (ReportedNode)
1040 R->addRange(R: ReportedNode->getSourceRange());
1041 C.emitReport(R: std::move(R));
1042}
1043
1044PathDiagnosticPieceRef DynamicTypePropagation::GenericsBugVisitor::VisitNode(
1045 const ExplodedNode *N, BugReporterContext &BRC,
1046 PathSensitiveBugReport &BR) {
1047 ProgramStateRef state = N->getState();
1048 ProgramStateRef statePrev = N->getFirstPred()->getState();
1049
1050 const ObjCObjectPointerType *const *TrackedType =
1051 state->get<MostSpecializedTypeArgsMap>(key: Sym);
1052 const ObjCObjectPointerType *const *TrackedTypePrev =
1053 statePrev->get<MostSpecializedTypeArgsMap>(key: Sym);
1054 if (!TrackedType)
1055 return nullptr;
1056
1057 if (TrackedTypePrev && *TrackedTypePrev == *TrackedType)
1058 return nullptr;
1059
1060 // Retrieve the associated statement.
1061 const Stmt *S = N->getStmtForDiagnostics();
1062 if (!S)
1063 return nullptr;
1064
1065 const LangOptions &LangOpts = BRC.getASTContext().getLangOpts();
1066
1067 SmallString<256> Buf;
1068 llvm::raw_svector_ostream OS(Buf);
1069 OS << "Type '";
1070 QualType::print(ty: *TrackedType, qs: Qualifiers(), OS, policy: LangOpts, PlaceHolder: llvm::Twine());
1071 OS << "' is inferred from ";
1072
1073 if (const auto *ExplicitCast = dyn_cast<ExplicitCastExpr>(Val: S)) {
1074 OS << "explicit cast (from '";
1075 QualType::print(ty: ExplicitCast->getSubExpr()->getType().getTypePtr(),
1076 qs: Qualifiers(), OS, policy: LangOpts, PlaceHolder: llvm::Twine());
1077 OS << "' to '";
1078 QualType::print(ty: ExplicitCast->getType().getTypePtr(), qs: Qualifiers(), OS,
1079 policy: LangOpts, PlaceHolder: llvm::Twine());
1080 OS << "')";
1081 } else if (const auto *ImplicitCast = dyn_cast<ImplicitCastExpr>(Val: S)) {
1082 OS << "implicit cast (from '";
1083 QualType::print(ty: ImplicitCast->getSubExpr()->getType().getTypePtr(),
1084 qs: Qualifiers(), OS, policy: LangOpts, PlaceHolder: llvm::Twine());
1085 OS << "' to '";
1086 QualType::print(ty: ImplicitCast->getType().getTypePtr(), qs: Qualifiers(), OS,
1087 policy: LangOpts, PlaceHolder: llvm::Twine());
1088 OS << "')";
1089 } else {
1090 OS << "this context";
1091 }
1092
1093 // Generate the extra diagnostic.
1094 PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
1095 N->getLocationContext());
1096 return std::make_shared<PathDiagnosticEventPiece>(args&: Pos, args: OS.str(), args: true);
1097}
1098
1099/// Register checkers.
1100void ento::registerObjCGenericsChecker(CheckerManager &Mgr) {
1101 Mgr.getChecker<DynamicTypePropagation>()->ObjCGenericsChecker.enable(Mgr);
1102}
1103
1104bool ento::shouldRegisterObjCGenericsChecker(const CheckerManager &) {
1105 return true;
1106}
1107
1108void ento::registerDynamicTypePropagation(CheckerManager &Mgr) {
1109 // The checker 'core.DynamicTypeChecker' relies on the modeling implemented
1110 // in the class 'DynamicTypePropagation', so this "modeling checker" can
1111 // register the 'DynamicTypePropagation' backend for its callbacks without
1112 // enabling its frontend.
1113 Mgr.getChecker<DynamicTypePropagation>();
1114}
1115
1116bool ento::shouldRegisterDynamicTypePropagation(const CheckerManager &) {
1117 return true;
1118}
1119