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