1//===- CastValueChecker - Model implementation of custom RTTIs --*- 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 defines CastValueChecker which models casts of custom RTTIs.
10//
11// TODO list:
12// - It only allows one succesful cast between two types however in the wild
13//   the object could be casted to multiple types.
14// - It needs to check the most likely type information from the dynamic type
15//   map to increase precision of dynamic casting.
16//
17//===----------------------------------------------------------------------===//
18
19#include "clang/AST/DeclTemplate.h"
20#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
21#include "clang/StaticAnalyzer/Core/Checker.h"
22#include "clang/StaticAnalyzer/Core/CheckerManager.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
24#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
25#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
26#include "llvm/ADT/Optional.h"
27#include <utility>
28
29using namespace clang;
30using namespace ento;
31
32namespace {
33class CastValueChecker : public Checker<check::DeadSymbols, eval::Call> {
34  enum class CallKind { Function, Method, InstanceOf };
35
36  using CastCheck =
37      std::function<void(const CastValueChecker *, const CallEvent &Call,
38                         DefinedOrUnknownSVal, CheckerContext &)>;
39
40public:
41  // We have five cases to evaluate a cast:
42  // 1) The parameter is non-null, the return value is non-null.
43  // 2) The parameter is non-null, the return value is null.
44  // 3) The parameter is null, the return value is null.
45  // cast: 1;  dyn_cast: 1, 2;  cast_or_null: 1, 3;  dyn_cast_or_null: 1, 2, 3.
46  //
47  // 4) castAs: Has no parameter, the return value is non-null.
48  // 5) getAs:  Has no parameter, the return value is null or non-null.
49  //
50  // We have two cases to check the parameter is an instance of the given type.
51  // 1) isa:             The parameter is non-null, returns boolean.
52  // 2) isa_and_nonnull: The parameter is null or non-null, returns boolean.
53  bool evalCall(const CallEvent &Call, CheckerContext &C) const;
54  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
55
56private:
57  // These are known in the LLVM project. The pairs are in the following form:
58  // {{{namespace, call}, argument-count}, {callback, kind}}
59  const CallDescriptionMap<std::pair<CastCheck, CallKind>> CDM = {
60      {{{"llvm", "cast"}, 1},
61       {&CastValueChecker::evalCast, CallKind::Function}},
62      {{{"llvm", "dyn_cast"}, 1},
63       {&CastValueChecker::evalDynCast, CallKind::Function}},
64      {{{"llvm", "cast_or_null"}, 1},
65       {&CastValueChecker::evalCastOrNull, CallKind::Function}},
66      {{{"llvm", "dyn_cast_or_null"}, 1},
67       {&CastValueChecker::evalDynCastOrNull, CallKind::Function}},
68      {{{"clang", "castAs"}, 0},
69       {&CastValueChecker::evalCastAs, CallKind::Method}},
70      {{{"clang", "getAs"}, 0},
71       {&CastValueChecker::evalGetAs, CallKind::Method}},
72      {{{"llvm", "isa"}, 1},
73       {&CastValueChecker::evalIsa, CallKind::InstanceOf}},
74      {{{"llvm", "isa_and_nonnull"}, 1},
75       {&CastValueChecker::evalIsaAndNonNull, CallKind::InstanceOf}}};
76
77  void evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
78                CheckerContext &C) const;
79  void evalDynCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
80                   CheckerContext &C) const;
81  void evalCastOrNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
82                      CheckerContext &C) const;
83  void evalDynCastOrNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
84                         CheckerContext &C) const;
85  void evalCastAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
86                  CheckerContext &C) const;
87  void evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
88                 CheckerContext &C) const;
89  void evalIsa(const CallEvent &Call, DefinedOrUnknownSVal DV,
90               CheckerContext &C) const;
91  void evalIsaAndNonNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
92                         CheckerContext &C) const;
93};
94} // namespace
95
96static bool isInfeasibleCast(const DynamicCastInfo *CastInfo,
97                             bool CastSucceeds) {
98  if (!CastInfo)
99    return false;
100
101  return CastSucceeds ? CastInfo->fails() : CastInfo->succeeds();
102}
103
104static const NoteTag *getNoteTag(CheckerContext &C,
105                                 const DynamicCastInfo *CastInfo,
106                                 QualType CastToTy, const Expr *Object,
107                                 bool CastSucceeds, bool IsKnownCast) {
108  std::string CastToName =
109      CastInfo ? CastInfo->to()->getAsCXXRecordDecl()->getNameAsString()
110               : CastToTy->getPointeeCXXRecordDecl()->getNameAsString();
111  Object = Object->IgnoreParenImpCasts();
112
113  return C.getNoteTag(
114      [=]() -> std::string {
115        SmallString<128> Msg;
116        llvm::raw_svector_ostream Out(Msg);
117
118        if (!IsKnownCast)
119          Out << "Assuming ";
120
121        if (const auto *DRE = dyn_cast<DeclRefExpr>(Object)) {
122          Out << '\'' << DRE->getDecl()->getNameAsString() << '\'';
123        } else if (const auto *ME = dyn_cast<MemberExpr>(Object)) {
124          Out << (IsKnownCast ? "Field '" : "field '")
125              << ME->getMemberDecl()->getNameAsString() << '\'';
126        } else {
127          Out << (IsKnownCast ? "The object" : "the object");
128        }
129
130        Out << ' ' << (CastSucceeds ? "is a" : "is not a") << " '" << CastToName
131            << '\'';
132
133        return std::string(Out.str());
134      },
135      /*IsPrunable=*/true);
136}
137
138static const NoteTag *getNoteTag(CheckerContext &C,
139                                 SmallVector<QualType, 4> CastToTyVec,
140                                 const Expr *Object,
141                                 bool IsKnownCast) {
142  Object = Object->IgnoreParenImpCasts();
143
144  return C.getNoteTag(
145      [=]() -> std::string {
146        SmallString<128> Msg;
147        llvm::raw_svector_ostream Out(Msg);
148
149        if (!IsKnownCast)
150          Out << "Assuming ";
151
152        if (const auto *DRE = dyn_cast<DeclRefExpr>(Object)) {
153          Out << '\'' << DRE->getDecl()->getNameAsString() << '\'';
154        } else if (const auto *ME = dyn_cast<MemberExpr>(Object)) {
155          Out << (IsKnownCast ? "Field '" : "field '")
156              << ME->getMemberDecl()->getNameAsString() << '\'';
157        } else {
158          Out << (IsKnownCast ? "The object" : "the object");
159        }
160        Out << " is";
161
162        bool First = true;
163        for (QualType CastToTy: CastToTyVec) {
164          std::string CastToName =
165            CastToTy->getAsCXXRecordDecl() ?
166            CastToTy->getAsCXXRecordDecl()->getNameAsString() :
167            CastToTy->getPointeeCXXRecordDecl()->getNameAsString();
168          Out << ' ' << ((CastToTyVec.size() == 1) ? "not" :
169                         (First ? "neither" : "nor")) << " a '" << CastToName
170              << '\'';
171          First = false;
172        }
173
174        return std::string(Out.str());
175      },
176      /*IsPrunable=*/true);
177}
178
179//===----------------------------------------------------------------------===//
180// Main logic to evaluate a cast.
181//===----------------------------------------------------------------------===//
182
183static QualType alignReferenceTypes(QualType toAlign, QualType alignTowards,
184                                    ASTContext &ACtx) {
185  if (alignTowards->isLValueReferenceType() &&
186      alignTowards.isConstQualified()) {
187    toAlign.addConst();
188    return ACtx.getLValueReferenceType(toAlign);
189  } else if (alignTowards->isLValueReferenceType())
190    return ACtx.getLValueReferenceType(toAlign);
191  else if (alignTowards->isRValueReferenceType())
192    return ACtx.getRValueReferenceType(toAlign);
193
194  llvm_unreachable("Must align towards a reference type!");
195}
196
197static void addCastTransition(const CallEvent &Call, DefinedOrUnknownSVal DV,
198                              CheckerContext &C, bool IsNonNullParam,
199                              bool IsNonNullReturn,
200                              bool IsCheckedCast = false) {
201  ProgramStateRef State = C.getState()->assume(DV, IsNonNullParam);
202  if (!State)
203    return;
204
205  const Expr *Object;
206  QualType CastFromTy;
207  QualType CastToTy = Call.getResultType();
208
209  if (Call.getNumArgs() > 0) {
210    Object = Call.getArgExpr(0);
211    CastFromTy = Call.parameters()[0]->getType();
212  } else {
213    Object = cast<CXXInstanceCall>(&Call)->getCXXThisExpr();
214    CastFromTy = Object->getType();
215    if (CastToTy->isPointerType()) {
216      if (!CastFromTy->isPointerType())
217        return;
218    } else {
219      if (!CastFromTy->isReferenceType())
220        return;
221
222      CastFromTy = alignReferenceTypes(CastFromTy, CastToTy, C.getASTContext());
223    }
224  }
225
226  const MemRegion *MR = DV.getAsRegion();
227  const DynamicCastInfo *CastInfo =
228      getDynamicCastInfo(State, MR, CastFromTy, CastToTy);
229
230  // We assume that every checked cast succeeds.
231  bool CastSucceeds = IsCheckedCast || CastFromTy == CastToTy;
232  if (!CastSucceeds) {
233    if (CastInfo)
234      CastSucceeds = IsNonNullReturn && CastInfo->succeeds();
235    else
236      CastSucceeds = IsNonNullReturn;
237  }
238
239  // Check for infeasible casts.
240  if (isInfeasibleCast(CastInfo, CastSucceeds)) {
241    C.generateSink(State, C.getPredecessor());
242    return;
243  }
244
245  // Store the type and the cast information.
246  bool IsKnownCast = CastInfo || IsCheckedCast || CastFromTy == CastToTy;
247  if (!IsKnownCast || IsCheckedCast)
248    State = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,
249                                      CastSucceeds);
250
251  SVal V = CastSucceeds ? C.getSValBuilder().evalCast(DV, CastToTy, CastFromTy)
252                        : C.getSValBuilder().makeNull();
253  C.addTransition(
254      State->BindExpr(Call.getOriginExpr(), C.getLocationContext(), V, false),
255      getNoteTag(C, CastInfo, CastToTy, Object, CastSucceeds, IsKnownCast));
256}
257
258static void addInstanceOfTransition(const CallEvent &Call,
259                                    DefinedOrUnknownSVal DV,
260                                    ProgramStateRef State, CheckerContext &C,
261                                    bool IsInstanceOf) {
262  const FunctionDecl *FD = Call.getDecl()->getAsFunction();
263  QualType CastFromTy = Call.parameters()[0]->getType();
264  SmallVector<QualType, 4> CastToTyVec;
265  for (unsigned idx = 0; idx < FD->getTemplateSpecializationArgs()->size() - 1;
266       ++idx) {
267    TemplateArgument CastToTempArg =
268      FD->getTemplateSpecializationArgs()->get(idx);
269    switch (CastToTempArg.getKind()) {
270    default:
271      return;
272    case TemplateArgument::Type:
273      CastToTyVec.push_back(CastToTempArg.getAsType());
274      break;
275    case TemplateArgument::Pack:
276      for (TemplateArgument ArgInPack: CastToTempArg.pack_elements())
277        CastToTyVec.push_back(ArgInPack.getAsType());
278      break;
279    }
280  }
281
282  const MemRegion *MR = DV.getAsRegion();
283  if (MR && CastFromTy->isReferenceType())
284    MR = State->getSVal(DV.castAs<Loc>()).getAsRegion();
285
286  bool Success = false;
287  bool IsAnyKnown = false;
288  for (QualType CastToTy: CastToTyVec) {
289    if (CastFromTy->isPointerType())
290      CastToTy = C.getASTContext().getPointerType(CastToTy);
291    else if (CastFromTy->isReferenceType())
292      CastToTy = alignReferenceTypes(CastToTy, CastFromTy, C.getASTContext());
293    else
294      return;
295
296    const DynamicCastInfo *CastInfo =
297      getDynamicCastInfo(State, MR, CastFromTy, CastToTy);
298
299    bool CastSucceeds;
300    if (CastInfo)
301      CastSucceeds = IsInstanceOf && CastInfo->succeeds();
302    else
303      CastSucceeds = IsInstanceOf || CastFromTy == CastToTy;
304
305    // Store the type and the cast information.
306    bool IsKnownCast = CastInfo || CastFromTy == CastToTy;
307    IsAnyKnown = IsAnyKnown || IsKnownCast;
308    ProgramStateRef NewState = State;
309    if (!IsKnownCast)
310      NewState = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,
311                                           IsInstanceOf);
312
313    if (CastSucceeds) {
314      Success = true;
315      C.addTransition(
316          NewState->BindExpr(Call.getOriginExpr(), C.getLocationContext(),
317                             C.getSValBuilder().makeTruthVal(true)),
318          getNoteTag(C, CastInfo, CastToTy, Call.getArgExpr(0), true,
319                     IsKnownCast));
320      if (IsKnownCast)
321        return;
322    } else if (CastInfo && CastInfo->succeeds()) {
323      C.generateSink(NewState, C.getPredecessor());
324      return;
325    }
326  }
327
328  if (!Success) {
329    C.addTransition(
330        State->BindExpr(Call.getOriginExpr(), C.getLocationContext(),
331                        C.getSValBuilder().makeTruthVal(false)),
332        getNoteTag(C, CastToTyVec, Call.getArgExpr(0), IsAnyKnown));
333  }
334}
335
336//===----------------------------------------------------------------------===//
337// Evaluating cast, dyn_cast, cast_or_null, dyn_cast_or_null.
338//===----------------------------------------------------------------------===//
339
340static void evalNonNullParamNonNullReturn(const CallEvent &Call,
341                                          DefinedOrUnknownSVal DV,
342                                          CheckerContext &C,
343                                          bool IsCheckedCast = false) {
344  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
345                    /*IsNonNullReturn=*/true, IsCheckedCast);
346}
347
348static void evalNonNullParamNullReturn(const CallEvent &Call,
349                                       DefinedOrUnknownSVal DV,
350                                       CheckerContext &C) {
351  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
352                    /*IsNonNullReturn=*/false);
353}
354
355static void evalNullParamNullReturn(const CallEvent &Call,
356                                    DefinedOrUnknownSVal DV,
357                                    CheckerContext &C) {
358  if (ProgramStateRef State = C.getState()->assume(DV, false))
359    C.addTransition(State->BindExpr(Call.getOriginExpr(),
360                                    C.getLocationContext(),
361                                    C.getSValBuilder().makeNull(), false),
362                    C.getNoteTag("Assuming null pointer is passed into cast",
363                                 /*IsPrunable=*/true));
364}
365
366void CastValueChecker::evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
367                                CheckerContext &C) const {
368  evalNonNullParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
369}
370
371void CastValueChecker::evalDynCast(const CallEvent &Call,
372                                   DefinedOrUnknownSVal DV,
373                                   CheckerContext &C) const {
374  evalNonNullParamNonNullReturn(Call, DV, C);
375  evalNonNullParamNullReturn(Call, DV, C);
376}
377
378void CastValueChecker::evalCastOrNull(const CallEvent &Call,
379                                      DefinedOrUnknownSVal DV,
380                                      CheckerContext &C) const {
381  evalNonNullParamNonNullReturn(Call, DV, C);
382  evalNullParamNullReturn(Call, DV, C);
383}
384
385void CastValueChecker::evalDynCastOrNull(const CallEvent &Call,
386                                         DefinedOrUnknownSVal DV,
387                                         CheckerContext &C) const {
388  evalNonNullParamNonNullReturn(Call, DV, C);
389  evalNonNullParamNullReturn(Call, DV, C);
390  evalNullParamNullReturn(Call, DV, C);
391}
392
393//===----------------------------------------------------------------------===//
394// Evaluating castAs, getAs.
395//===----------------------------------------------------------------------===//
396
397static void evalZeroParamNonNullReturn(const CallEvent &Call,
398                                       DefinedOrUnknownSVal DV,
399                                       CheckerContext &C,
400                                       bool IsCheckedCast = false) {
401  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
402                    /*IsNonNullReturn=*/true, IsCheckedCast);
403}
404
405static void evalZeroParamNullReturn(const CallEvent &Call,
406                                    DefinedOrUnknownSVal DV,
407                                    CheckerContext &C) {
408  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
409                    /*IsNonNullReturn=*/false);
410}
411
412void CastValueChecker::evalCastAs(const CallEvent &Call,
413                                  DefinedOrUnknownSVal DV,
414                                  CheckerContext &C) const {
415  evalZeroParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
416}
417
418void CastValueChecker::evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
419                                 CheckerContext &C) const {
420  evalZeroParamNonNullReturn(Call, DV, C);
421  evalZeroParamNullReturn(Call, DV, C);
422}
423
424//===----------------------------------------------------------------------===//
425// Evaluating isa, isa_and_nonnull.
426//===----------------------------------------------------------------------===//
427
428void CastValueChecker::evalIsa(const CallEvent &Call, DefinedOrUnknownSVal DV,
429                               CheckerContext &C) const {
430  ProgramStateRef NonNullState, NullState;
431  std::tie(NonNullState, NullState) = C.getState()->assume(DV);
432
433  if (NonNullState) {
434    addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/true);
435    addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/false);
436  }
437
438  if (NullState) {
439    C.generateSink(NullState, C.getPredecessor());
440  }
441}
442
443void CastValueChecker::evalIsaAndNonNull(const CallEvent &Call,
444                                         DefinedOrUnknownSVal DV,
445                                         CheckerContext &C) const {
446  ProgramStateRef NonNullState, NullState;
447  std::tie(NonNullState, NullState) = C.getState()->assume(DV);
448
449  if (NonNullState) {
450    addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/true);
451    addInstanceOfTransition(Call, DV, NonNullState, C, /*IsInstanceOf=*/false);
452  }
453
454  if (NullState) {
455    addInstanceOfTransition(Call, DV, NullState, C, /*IsInstanceOf=*/false);
456  }
457}
458
459//===----------------------------------------------------------------------===//
460// Main logic to evaluate a call.
461//===----------------------------------------------------------------------===//
462
463bool CastValueChecker::evalCall(const CallEvent &Call,
464                                CheckerContext &C) const {
465  const auto *Lookup = CDM.lookup(Call);
466  if (!Lookup)
467    return false;
468
469  const CastCheck &Check = Lookup->first;
470  CallKind Kind = Lookup->second;
471
472  Optional<DefinedOrUnknownSVal> DV;
473
474  switch (Kind) {
475  case CallKind::Function: {
476    // We only model casts from pointers to pointers or from references
477    // to references. Other casts are most likely specialized and we
478    // cannot model them.
479    QualType ParamT = Call.parameters()[0]->getType();
480    QualType ResultT = Call.getResultType();
481    if (!(ParamT->isPointerType() && ResultT->isPointerType()) &&
482        !(ParamT->isReferenceType() && ResultT->isReferenceType())) {
483      return false;
484    }
485
486    DV = Call.getArgSVal(0).getAs<DefinedOrUnknownSVal>();
487    break;
488  }
489  case CallKind::InstanceOf: {
490    // We need to obtain the only template argument to determinte the type.
491    const FunctionDecl *FD = Call.getDecl()->getAsFunction();
492    if (!FD || !FD->getTemplateSpecializationArgs())
493      return false;
494
495    DV = Call.getArgSVal(0).getAs<DefinedOrUnknownSVal>();
496    break;
497  }
498  case CallKind::Method:
499    const auto *InstanceCall = dyn_cast<CXXInstanceCall>(&Call);
500    if (!InstanceCall)
501      return false;
502
503    DV = InstanceCall->getCXXThisVal().getAs<DefinedOrUnknownSVal>();
504    break;
505  }
506
507  if (!DV)
508    return false;
509
510  Check(this, Call, *DV, C);
511  return true;
512}
513
514void CastValueChecker::checkDeadSymbols(SymbolReaper &SR,
515                                        CheckerContext &C) const {
516  C.addTransition(removeDeadCasts(C.getState(), SR));
517}
518
519void ento::registerCastValueChecker(CheckerManager &Mgr) {
520  Mgr.registerChecker<CastValueChecker>();
521}
522
523bool ento::shouldRegisterCastValueChecker(const CheckerManager &mgr) {
524  return true;
525}
526