Clang Project

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