Index: clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h +++ clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h @@ -20,6 +20,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/StringRef.h" #include @@ -390,7 +391,7 @@ /// The visitor detects NoteTags and displays the event notes they contain. -class TagVisitor : public BugReporterVisitor { +class TagVisitor final : public BugReporterVisitor { public: void Profile(llvm::FoldingSetNodeID &ID) const override; @@ -399,6 +400,24 @@ PathSensitiveBugReport &R) override; }; +/// It detects evaluated casts and suppresses false assumption based reports. +class CastVisitor final : public BugReporterVisitor { + using RegionSetTy = llvm::SmallSet; + RegionSetTy RegionSet; + +public: + static void *getTag(); + + PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, + BugReporterContext &BRC, + PathSensitiveBugReport &R) override; + + void finalizeVisitor(BugReporterContext &BRC, const ExplodedNode *N, + PathSensitiveBugReport &BR) override; + + void Profile(llvm::FoldingSetNodeID &ID) const override; +}; + } // namespace ento } // namespace clang Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicCastInfo.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicCastInfo.h +++ /dev/null @@ -1,55 +0,0 @@ -//===- DynamicCastInfo.h - Runtime cast information -------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICCASTINFO_H -#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICCASTINFO_H - -#include "clang/AST/Type.h" - -namespace clang { -namespace ento { - -class DynamicCastInfo { -public: - enum CastResult { Success, Failure }; - - DynamicCastInfo(QualType from, QualType to, CastResult resultKind) - : From(from), To(to), ResultKind(resultKind) {} - - QualType from() const { return From; } - QualType to() const { return To; } - - bool equals(QualType from, QualType to) const { - return From == from && To == to; - } - - bool succeeds() const { return ResultKind == CastResult::Success; } - bool fails() const { return ResultKind == CastResult::Failure; } - - bool operator==(const DynamicCastInfo &RHS) const { - return From == RHS.From && To == RHS.To; - } - bool operator<(const DynamicCastInfo &RHS) const { - return From < RHS.From && To < RHS.To; - } - - void Profile(llvm::FoldingSetNodeID &ID) const { - ID.Add(From); - ID.Add(To); - ID.AddInteger(ResultKind); - } - -private: - QualType From, To; - CastResult ResultKind; -}; - -} // namespace ento -} // namespace clang - -#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICCASTINFO_H Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h +++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h @@ -16,7 +16,6 @@ #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICTYPE_H #include "clang/AST/Type.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicCastInfo.h" #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" @@ -25,11 +24,23 @@ #include "llvm/ADT/ImmutableMap.h" #include "llvm/ADT/Optional.h" #include +#include namespace clang { namespace ento { -/// Get dynamic type information for the region \p MR. +/// \returns Whether the record of type \p X is derived from the record of type +/// \p Y. +bool isDerivedFrom(QualType X, QualType Y); + +/// \returns Whether the record of type \p X is equal to the record of type \p +/// Y or one record is derived from the other record. +bool isOneEqualOrDerivedFromOther(QualType X, QualType Y); + +/// \returns Whether an infeasible cast found. +bool isInfeasibleCastFound(ProgramStateRef State, const MemRegion *MR, + const std::vector &Records); + Optional getDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR); @@ -37,11 +48,12 @@ Optional getStoredDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR); -/// Get dynamic cast information from \p CastFromTy to \p CastToTy of \p MR. -Optional getDynamicCastInfo(ProgramStateRef State, - const MemRegion *MR, - QualType CastFromTy, - QualType CastToTy); +/// Get dynamic type information of the failed cast for the region \p MR. +/// The cast failed whether the current casting to \p CastToTy has a record type +/// which derives from a previously stored cast's record type. +Optional getFailedCastInfo(ProgramStateRef State, + const MemRegion *MR, + QualType CastToTy); /// Set dynamic type information of the region; return the new state. ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, @@ -52,11 +64,12 @@ QualType NewTy, bool CanBeSubClassed = true); /// Set dynamic type and cast information of the region; return the new state. -ProgramStateRef setDynamicTypeAndCastInfo(ProgramStateRef State, - const MemRegion *MR, - QualType CastFromTy, - QualType CastToTy, - bool IsCastSucceeds); +/// It stores the largest set what is the record of the given type \p CastToTy +/// cannot be, and what is the most-derived class which the record could be. +/// It also stores the succeeded casts. +ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, + QualType CastToTy, bool CastSucceeds, + Optional CastInfo); /// Removes the dead type informations from \p State. ProgramStateRef removeDeadTypes(ProgramStateRef State, SymbolReaper &SR); Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h +++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h @@ -18,32 +18,30 @@ /// of a region in a given state along the analysis path. class DynamicTypeInfo { public: - DynamicTypeInfo() : DynTy(QualType()) {} + DynamicTypeInfo() : Ty(QualType()) {} - DynamicTypeInfo(QualType Ty, bool CanBeSub = true) - : DynTy(Ty), CanBeASubClass(CanBeSub) {} + DynamicTypeInfo(QualType Ty, bool CanBeASubClass = true) + : Ty(Ty), CanBeASubClass(CanBeASubClass) {} - /// Returns false if the type information is precise (the type 'DynTy' is + /// Returns false if the type information is precise (the type 'Ty' is /// the only type in the lattice), true otherwise. bool canBeASubClass() const { return CanBeASubClass; } - /// Returns true if the dynamic type info is available. - bool isValid() const { return !DynTy.isNull(); } - /// Returns the currently inferred upper bound on the runtime type. - QualType getType() const { return DynTy; } + QualType getType() const { return Ty; } bool operator==(const DynamicTypeInfo &RHS) const { - return DynTy == RHS.DynTy && CanBeASubClass == RHS.CanBeASubClass; + return Ty == RHS.Ty && CanBeASubClass == RHS.CanBeASubClass; } + bool operator<(const DynamicTypeInfo &RHS) const { return Ty < RHS.Ty; } void Profile(llvm::FoldingSetNodeID &ID) const { - ID.Add(DynTy); + ID.Add(Ty); ID.AddBoolean(CanBeASubClass); } private: - QualType DynTy; + QualType Ty; bool CanBeASubClass; }; Index: clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp +++ clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp @@ -8,12 +8,6 @@ // // This defines CastValueChecker which models casts of custom RTTIs. // -// TODO list: -// - It only allows one succesful cast between two types however in the wild -// the object could be casted to multiple types. -// - It needs to check the most likely type information from the dynamic type -// map to increase precision of dynamic casting. -// //===----------------------------------------------------------------------===// #include "clang/AST/DeclTemplate.h" @@ -92,21 +86,109 @@ }; } // namespace -static bool isInfeasibleCast(Optional CastInfo, - bool CastSucceeds) { - if (!CastInfo) +// Dynamic type: Denote 'r' the 'MemoryRegion' which we try to cast. We store +// the most derived record type information in the 'DynamicTypeMap' for the +// given 'r'. We store the record types which the given 'r' cannot be casted +// to in 'FailedCastMap'. Every 'MemoryRegion' is typeless from the checker's +// point of view, because it waits for a cast expression to denote the object +// with an appropriate type. +// Denote 'S(r)' a 'MemoryRegion' 'r' entry in 'DynamicTypeMap', and +// denote 'F(r)' a 'MemoryRegion' 'r' entry in 'FailedCastMap'. +// +// Record: For the given 'MemoryRegion' 'r' we obtain the records from the AST +// using the cast expression's and the object's static types and also the +// dynamically known types using 'S(r)' and 'F(r)'. +// +// Inheritance: for two given records 'X' and 'Y' let us call 'X' inherits from +// 'Y' if there exists at least one directed path from 'X' to 'Y'. +// Denote it by 'X -> Y'. +// +// Related records: for two given records 'X' and 'Y' let us call them related +// if either X = Y, or 'X' inherits from 'Y', or 'Y' inherits from 'X'. +// Denote it by 'X <-> Y'. ('X <-> Y' <=> 'X -> Y' ∧ 'X <- Y'.) +// +// Cast: for two given related records 'X' and 'Y' (X <-> Y) we define two +// types of casts: the downcast: 'X -> Y', and the upcast: 'X <- Y'. +// +// Succeeded-cast path: For the given static type of a given MemoryRegion 'r' +// we try to chain the succeeded casts to form a directed path from the +// static type to the most derived record type information in 'S(r)'. +// +// An 'X -> Y' downcast/upcast succeeds for an 'r' 'MemoryRegion' iff +// - 'X <-> Y' and, +// - 'Y' ∉ 'F(r)' and: +// - If ∄S(r): it succeeds as a first entry. +// - If ∃S(r): +// - If ∃'S(r) <-> Y': it succeeds as the succeeded-cast path continues. +// - If ∄'S(r) <-> Y': we could assume that it succeeds as 'Y' could create +// a succeeded-cast path later during the execution. +// +// Here the known static types are \p CastFromTy and \p CastToTy. The 'S(r)' +// entry is \p SucceededCastInfo and the 'F(r)' entry is \p FailedCastInfo. +static Optional +isSuccededCast(Optional SucceededCastInfo, + Optional FailedCastInfo, QualType CastFromTy, + QualType CastToTy) { + if (FailedCastInfo || !isOneEqualOrDerivedFromOther(CastFromTy, CastToTy)) return false; - return CastSucceeds ? CastInfo->fails() : CastInfo->succeeds(); + if (!SucceededCastInfo) + return true; + + if (isOneEqualOrDerivedFromOther(SucceededCastInfo->getType(), CastToTy)) + return true; + + return None; } -static const NoteTag *getNoteTag(CheckerContext &C, - Optional CastInfo, - QualType CastToTy, const Expr *Object, - bool CastSucceeds, bool IsKnownCast) { +namespace { +struct CastContext { + CastContext(ProgramStateRef State, const MemRegion *MR, QualType CastFromTy, + QualType CastToTy, bool Assumption, bool IsCheckedCast) { + Optional SucceededCastInfo = + getStoredDynamicTypeInfo(State, MR); + + Optional FailedCastInfo = + getFailedCastInfo(State, MR, CastToTy); + + // We assume that every checked cast (cast<>) succeeds. + bool IsAlwaysSucceeds = + IsCheckedCast || CastFromTy->getPointeeCXXRecordDecl() == + CastToTy->getPointeeCXXRecordDecl(); + + if (IsAlwaysSucceeds) { + CastSucceeds = true; + IsKnownCast = true; + } else if (Optional TempCastSucceeds = isSuccededCast( + SucceededCastInfo, FailedCastInfo, CastFromTy, CastToTy)) { + CastSucceeds = Assumption && *TempCastSucceeds; + IsKnownCast = (CastSucceeds && SucceededCastInfo && + isDerivedFrom(SucceededCastInfo->getType(), CastToTy)) || + (!CastSucceeds && FailedCastInfo && + isDerivedFrom(FailedCastInfo->getType(), CastToTy)); + } else { + CastSucceeds = Assumption; + IsKnownCast = false; + } + + CastInfo = CastSucceeds ? SucceededCastInfo : FailedCastInfo; + } + + bool CastSucceeds, IsKnownCast; + Optional CastInfo; +}; +} // namespace + +static const NoteTag *getNoteTag(CheckerContext &C, const Expr *Object, + QualType CastToTy, CastContext &CastCtx) { + QualType KnownCastToTy; + if (CastCtx.CastInfo && CastCtx.IsKnownCast) + KnownCastToTy = CastCtx.CastInfo->getType(); + std::string CastToName = - CastInfo ? CastInfo->to()->getPointeeCXXRecordDecl()->getNameAsString() - : CastToTy->getPointeeCXXRecordDecl()->getNameAsString(); + CastCtx.CastInfo && CastCtx.IsKnownCast + ? KnownCastToTy->getPointeeCXXRecordDecl()->getNameAsString() + : CastToTy->getPointeeCXXRecordDecl()->getNameAsString(); Object = Object->IgnoreParenImpCasts(); return C.getNoteTag( @@ -114,24 +196,24 @@ SmallString<128> Msg; llvm::raw_svector_ostream Out(Msg); - if (!IsKnownCast) + if (!CastCtx.IsKnownCast) Out << "Assuming "; if (const auto *DRE = dyn_cast(Object)) { Out << '\'' << DRE->getDecl()->getNameAsString() << '\''; } else if (const auto *ME = dyn_cast(Object)) { - Out << (IsKnownCast ? "Field '" : "field '") + Out << (CastCtx.IsKnownCast ? "Field '" : "field '") << ME->getMemberDecl()->getNameAsString() << '\''; } else { - Out << (IsKnownCast ? "The object" : "the object"); + Out << (CastCtx.IsKnownCast ? "The object" : "the object"); } - Out << ' ' << (CastSucceeds ? "is a" : "is not a") << " '" << CastToName - << '\''; + Out << ' ' << (CastCtx.CastSucceeds ? "is" : "is not") << " a '" + << CastToName << '\''; return Out.str(); }, - /*IsPrunable=*/true); + /*IsPrunable=*/!CastCtx.CastSucceeds); } //===----------------------------------------------------------------------===// @@ -157,8 +239,10 @@ bool IsNonNullReturn, bool IsCheckedCast = false) { ProgramStateRef State = C.getState()->assume(DV, IsNonNullParam); - if (!State) + if (!State) { + C.generateSink(C.getState(), C.getPredecessor()); return; + } const Expr *Object; QualType CastFromTy; @@ -182,35 +266,19 @@ } const MemRegion *MR = DV.getAsRegion(); - Optional CastInfo = - getDynamicCastInfo(State, MR, CastFromTy, CastToTy); - - // We assume that every checked cast succeeds. - bool CastSucceeds = IsCheckedCast || CastFromTy == CastToTy; - if (!CastSucceeds) { - if (CastInfo) - CastSucceeds = IsNonNullReturn && CastInfo->succeeds(); - else - CastSucceeds = IsNonNullReturn; - } + CastContext CastCtx(State, MR, CastFromTy, CastToTy, + /*Assumption=*/IsNonNullReturn, IsCheckedCast); - // Check for infeasible casts. - if (isInfeasibleCast(CastInfo, CastSucceeds)) { - C.generateSink(State, C.getPredecessor()); - return; - } + State = setDynamicTypeInfo(State, MR, CastToTy, CastCtx.CastSucceeds, + CastCtx.CastInfo); - // Store the type and the cast information. - bool IsKnownCast = CastInfo || IsCheckedCast || CastFromTy == CastToTy; - if (!IsKnownCast || IsCheckedCast) - State = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy, - CastSucceeds); + SVal V = CastCtx.CastSucceeds + ? C.getSValBuilder().evalCast(DV, CastToTy, CastFromTy) + : C.getSValBuilder().makeNull(); - SVal V = CastSucceeds ? C.getSValBuilder().evalCast(DV, CastToTy, CastFromTy) - : C.getSValBuilder().makeNull(); C.addTransition( State->BindExpr(Call.getOriginExpr(), C.getLocationContext(), V, false), - getNoteTag(C, CastInfo, CastToTy, Object, CastSucceeds, IsKnownCast)); + getNoteTag(C, Object, CastToTy, CastCtx)); } static void addInstanceOfTransition(const CallEvent &Call, @@ -218,8 +286,9 @@ ProgramStateRef State, CheckerContext &C, bool IsInstanceOf) { const FunctionDecl *FD = Call.getDecl()->getAsFunction(); - QualType CastFromTy = Call.parameters()[0]->getType(); + QualType CastFromTy = Call.parameters()[0]->getType().getCanonicalType(); QualType CastToTy = FD->getTemplateSpecializationArgs()->get(0).getAsType(); + if (CastFromTy->isPointerType()) CastToTy = C.getASTContext().getPointerType(CastToTy); else if (CastFromTy->isReferenceType()) @@ -228,31 +297,16 @@ return; const MemRegion *MR = DV.getAsRegion(); - Optional CastInfo = - getDynamicCastInfo(State, MR, CastFromTy, CastToTy); - - bool CastSucceeds; - if (CastInfo) - CastSucceeds = IsInstanceOf && CastInfo->succeeds(); - else - CastSucceeds = IsInstanceOf || CastFromTy == CastToTy; - - if (isInfeasibleCast(CastInfo, CastSucceeds)) { - C.generateSink(State, C.getPredecessor()); - return; - } + CastContext CastCtx(State, MR, CastFromTy, CastToTy, + /*Assumption=*/IsInstanceOf, /*IsCheckedCast=*/false); - // Store the type and the cast information. - bool IsKnownCast = CastInfo || CastFromTy == CastToTy; - if (!IsKnownCast) - State = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy, - IsInstanceOf); + State = setDynamicTypeInfo(State, MR, CastToTy, CastCtx.CastSucceeds, + CastCtx.CastInfo); C.addTransition( State->BindExpr(Call.getOriginExpr(), C.getLocationContext(), - C.getSValBuilder().makeTruthVal(CastSucceeds)), - getNoteTag(C, CastInfo, CastToTy, Call.getArgExpr(0), CastSucceeds, - IsKnownCast)); + C.getSValBuilder().makeTruthVal(CastCtx.CastSucceeds)), + getNoteTag(C, Call.getArgExpr(0), CastToTy, CastCtx)); } //===----------------------------------------------------------------------===// @@ -398,10 +452,10 @@ // We only model casts from pointers to pointers or from references // to references. Other casts are most likely specialized and we // cannot model them. - QualType ParamT = Call.parameters()[0]->getType(); - QualType ResultT = Call.getResultType(); - if (!(ParamT->isPointerType() && ResultT->isPointerType()) && - !(ParamT->isReferenceType() && ResultT->isReferenceType())) + QualType ParamTy = Call.parameters()[0]->getType(); + QualType ResultTy = Call.getResultType(); + if (!(ParamTy->isPointerType() && ResultTy->isPointerType()) && + !(ParamTy->isReferenceType() && ResultTy->isReferenceType())) return false; DV = Call.getArgSVal(0).getAs(); Index: clang/lib/StaticAnalyzer/Core/BugReporter.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/BugReporter.cpp +++ clang/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -2766,6 +2766,7 @@ R->addVisitor(std::make_unique()); R->addVisitor(std::make_unique()); R->addVisitor(std::make_unique()); + R->addVisitor(std::make_unique()); BugReporterContext BRC(Reporter); Index: clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp +++ clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp @@ -37,6 +37,7 @@ #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" @@ -63,6 +64,7 @@ #include #include #include +#include using namespace clang; using namespace ento; @@ -2899,3 +2901,77 @@ return nullptr; } + +//===----------------------------------------------------------------------===// +// Implementation of CastVisitor. +//===----------------------------------------------------------------------===// + +void CastVisitor::Profile(llvm::FoldingSetNodeID &ID) const { + ID.AddPointer(getTag()); +} + +void *CastVisitor::getTag() { + static int Tag = 0; + return static_cast(&Tag); +} + +PathDiagnosticPieceRef CastVisitor::VisitNode(const ExplodedNode *N, + BugReporterContext &BRC, + PathSensitiveBugReport &R) { + ProgramPoint PP = N->getLocation(); + if (!dyn_cast_or_null(PP.getTag())) + return nullptr; + + auto PS = PP.getAs(); + if (!PS) + return nullptr; + + ProgramStateRef State = N->getState(); + const LocationContext *LCtx = N->getLocationContext(); + CallEventRef<> Call = BRC.getStateManager().getCallEventManager().getCall( + PS->getStmt(), State, LCtx); + if (!Call) + return nullptr; + + DefinedOrUnknownSVal DV = UnknownVal(); + if (Call->getNumArgs() == 1) { + DV = Call->getArgSVal(0).castAs(); + } else if (const auto *InstanceCall = dyn_cast(Call)) { + DV = InstanceCall->getCXXThisVal().castAs(); + } else { + return nullptr; + } + + RegionSet.insert(DV.getAsRegion()); + return nullptr; +} + +void CastVisitor::finalizeVisitor(BugReporterContext &BRC, + const ExplodedNode *N, + PathSensitiveBugReport &R) { + if (RegionSet.empty()) + return; + + bool IsFalsePositive = false; + ProgramStateRef State = N->getState(); + std::vector Records; + + using namespace ast_matchers; + constexpr llvm::StringLiteral RecordName = "record"; + auto Matches = match(cxxRecordDecl().bind(RecordName), BRC.getASTContext()); + for (BoundNodes &Match : Matches) { + if (const auto *RD = Match.getNodeAs(RecordName)) { + if (RD->hasDefinition()) { + Records.push_back(RD); + } + } + } + + for (const MemRegion *MR : RegionSet) { + if ((IsFalsePositive = isInfeasibleCastFound(State, MR, Records))) + break; + } + + if (IsFalsePositive) + R.markInvalid(getTag(), nullptr); +} Index: clang/lib/StaticAnalyzer/Core/DynamicType.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/DynamicType.cpp +++ clang/lib/StaticAnalyzer/Core/DynamicType.cpp @@ -27,19 +27,72 @@ REGISTER_MAP_WITH_PROGRAMSTATE(DynamicTypeMap, const clang::ento::MemRegion *, clang::ento::DynamicTypeInfo) -/// A set factory of dynamic cast informations. -REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(CastSet, clang::ento::DynamicCastInfo) +/// A set factory of dynamic cast informations as type informations. +REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(CastSet, clang::ento::DynamicTypeInfo) -/// A map from symbols to cast informations. -REGISTER_MAP_WITH_PROGRAMSTATE(DynamicCastMap, const clang::ento::MemRegion *, +/// A map from symbols to succeeded cast informations. +REGISTER_MAP_WITH_PROGRAMSTATE(SucceededCastMap, const clang::ento::MemRegion *, + CastSet) + +/// A map from symbols to failed cast informations. +REGISTER_MAP_WITH_PROGRAMSTATE(FailedCastMap, const clang::ento::MemRegion *, CastSet) namespace clang { namespace ento { +static const MemRegion *getSimplifiedRegion(const MemRegion *MR) { + return MR->StripCasts(); +} + +bool isDerivedFrom(QualType X, QualType Y) { + const CXXRecordDecl *XRD = X->getPointeeCXXRecordDecl(); + const CXXRecordDecl *YRD = Y->getPointeeCXXRecordDecl(); + + if (!XRD || !YRD) + return false; + + return XRD->isDerivedFrom(YRD); +} + +bool isOneEqualOrDerivedFromOther(QualType X, QualType Y) { + if (X->getPointeeCXXRecordDecl() == Y->getPointeeCXXRecordDecl()) + return true; + + return isDerivedFrom(X, Y) || isDerivedFrom(Y, X); +} + +bool isInfeasibleCastFound(ProgramStateRef State, const MemRegion *MR, + const std::vector &Records) { + const CastSet *SucceededSet = State->get().lookup(MR); + if (!SucceededSet) + return false; + + for (const DynamicTypeInfo &I : *SucceededSet) { + for (const DynamicTypeInfo &J : *SucceededSet) { + // Pick two disjunct records (there is no direct path between them). + if (!isOneEqualOrDerivedFromOther(I.getType(), J.getType())) { + for (const CXXRecordDecl *RD : Records) { + // If the picked two records have a common descendant the cast is + // feasible into that descendant record. + if (RD->isDerivedFrom(I.getType()->getPointeeCXXRecordDecl()) && + RD->isDerivedFrom(J.getType()->getPointeeCXXRecordDecl())) { + return false; + } + } + // If the picked two records does not have a common descendant the cast + // is infeasible as the object could not be casted into both of them. + return true; + } + } + } + + return false; +} + Optional getDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR) { - MR = MR->StripCasts(); + MR = getSimplifiedRegion(MR); // Look up the dynamic type in the GDM. if (const DynamicTypeInfo *DTI = State->get(MR)) @@ -59,23 +112,36 @@ Optional getStoredDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR) { +if (!MR) + return None; + + MR = getSimplifiedRegion(MR); + if (const DynamicTypeInfo *DTI = State->get(MR)) return *DTI; return None; } -Optional getDynamicCastInfo(ProgramStateRef State, - const MemRegion *MR, - QualType CastFromTy, - QualType CastToTy) { - const auto *Lookup = State->get().lookup(MR); +Optional getFailedCastInfo(ProgramStateRef State, + const MemRegion *MR, + QualType CastToTy) { + if (!MR) + return None; + + MR = getSimplifiedRegion(MR); + const auto *Lookup = State->get().lookup(MR); if (!Lookup) return None; - for (const DynamicCastInfo &Cast : *Lookup) - if (Cast.equals(CastFromTy, CastToTy)) + for (const DynamicTypeInfo &Cast : *Lookup) { + QualType FailedCastTy = Cast.getType(); + if (FailedCastTy->getPointeeCXXRecordDecl() == + CastToTy->getPointeeCXXRecordDecl() || + isDerivedFrom(CastToTy, FailedCastTy)) { return Cast; + } + } return None; } @@ -92,32 +158,36 @@ return setDynamicTypeInfo(State, MR, DynamicTypeInfo(NewTy, CanBeSubClassed)); } -ProgramStateRef setDynamicTypeAndCastInfo(ProgramStateRef State, - const MemRegion *MR, - QualType CastFromTy, - QualType CastToTy, - bool CastSucceeds) { +ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, + QualType CastToTy, bool CastSucceeds, + Optional CastInfo) { if (!MR) return State; - if (CastSucceeds) { - assert((CastToTy->isAnyPointerType() || CastToTy->isReferenceType()) && - "DynamicTypeInfo should always be a pointer."); - State = State->set(MR, CastToTy); - } - - DynamicCastInfo::CastResult ResultKind = - CastSucceeds ? DynamicCastInfo::CastResult::Success - : DynamicCastInfo::CastResult::Failure; - + MR = getSimplifiedRegion(MR); CastSet::Factory &F = State->get_context(); + const CastSet *TempSet; + TempSet = CastSucceeds ? State->get(MR) + : State->get(MR); - const CastSet *TempSet = State->get(MR); CastSet Set = TempSet ? *TempSet : F.getEmptySet(); + Set = F.add(Set, CastToTy); - Set = F.add(Set, {CastFromTy, CastToTy, ResultKind}); - State = State->set(MR, Set); + if (CastSucceeds) { + // If there is no 'CastInfo' or the 'CastToTy' is a downcast store it. + // Downcast gives more precision what is the current most derived class. + if (!CastInfo || isDerivedFrom(CastToTy, CastInfo->getType())) { + State = setDynamicTypeInfo(State, MR, CastToTy); + } + } else { + // Upcast gives more precision what is the largest set the class cannot be. + if (CastInfo && isDerivedFrom(CastInfo->getType(), CastToTy)) { + Set = F.remove(Set, *CastInfo); + } + } + State = CastSucceeds ? State->set(MR, Set) + : State->set(MR, Set); assert(State); return State; } @@ -127,7 +197,7 @@ SymbolReaper &SR) { for (const auto &Elem : Map) if (!SR.isLiveRegion(Elem.first)) - State = State->remove(Elem.first); + State = State->remove(Elem.first); return State; } @@ -137,7 +207,7 @@ } ProgramStateRef removeDeadCasts(ProgramStateRef State, SymbolReaper &SR) { - return removeDead(State, State->get(), SR); + return removeDead(State, State->get(), SR); } static void printDynamicTypesJson(raw_ostream &Out, ProgramStateRef State, @@ -176,12 +246,10 @@ Indent(Out, Space, IsDot) << "]," << NL; } -static void printDynamicCastsJson(raw_ostream &Out, ProgramStateRef State, - const char *NL, unsigned int Space, - bool IsDot) { - Indent(Out, Space, IsDot) << "\"dynamic_casts\": "; - - const DynamicCastMapTy &Map = State->get(); +template +static void printCastsJson(raw_ostream &Out, ProgramStateRef State, + const MapTy &Map, const char *NL, unsigned int Space, + bool IsDot) { if (Map.isEmpty()) { Out << "null," << NL; return; @@ -189,7 +257,7 @@ ++Space; Out << '[' << NL; - for (DynamicCastMapTy::iterator I = Map.begin(); I != Map.end(); ++I) { + for (typename MapTy::iterator I = Map.begin(); I != Map.end(); ++I) { const MemRegion *MR = I->first; const CastSet &Set = I->second; @@ -199,16 +267,14 @@ } else { ++Space; Out << '[' << NL; + Indent(Out, Space, IsDot); for (CastSet::iterator SI = Set.begin(); SI != Set.end(); ++SI) { - Indent(Out, Space, IsDot) - << "{ \"from\": \"" << SI->from().getAsString() << "\", \"to\": \"" - << SI->to().getAsString() << "\", \"kind\": \"" - << (SI->succeeds() ? "success" : "fail") << "\" }"; + Out << '\"' << SI->getType().getAsString() << '\"'; if (std::next(SI) != Set.end()) - Out << ','; - Out << NL; + Out << ", "; } + Out << NL; --Space; Indent(Out, Space, IsDot) << ']'; } @@ -226,7 +292,12 @@ void printDynamicTypeInfoJson(raw_ostream &Out, ProgramStateRef State, const char *NL, unsigned int Space, bool IsDot) { printDynamicTypesJson(Out, State, NL, Space, IsDot); - printDynamicCastsJson(Out, State, NL, Space, IsDot); + + Indent(Out, Space, IsDot) << "\"succeeded_casts\": "; + printCastsJson(Out, State, State->get(), NL, Space, IsDot); + + Indent(Out, Space, IsDot) << "\"failed_casts\": "; + printCastsJson(Out, State, State->get(), NL, Space, IsDot); } } // namespace ento Index: clang/test/Analysis/cast-value-hierarchy-failures-set.cpp =================================================================== --- /dev/null +++ clang/test/Analysis/cast-value-hierarchy-failures-set.cpp @@ -0,0 +1,47 @@ +// RUN: %clang_analyze_cc1 \ +// RUN: -analyzer-checker=core,apiModeling.llvm.CastValue,debug.ExprInspection\ +// RUN: -verify %s 2>&1 | FileCheck %s + +// expected-no-diagnostics + +#include "Inputs/llvm.h" + +using namespace llvm; + +void clang_analyzer_printState(); + +struct A {}; // A +struct B : A {}; // `-B +struct C : B {}; // `-C +struct D : C {}; // `-D + +void test_downcast(const A *a) { + if (isa(a)) + return; + + clang_analyzer_printState(); + // CHECK: "failed_casts": [ + // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "casts": [ + // CHECK-NEXT: "struct C *" + // CHECK-NEXT: ]} + + // A failed upcast gives more precision what the type cannot be. + if (isa(a)) + return; + + clang_analyzer_printState(); + // CHECK: "failed_casts": [ + // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "casts": [ + // CHECK-NEXT: "struct B *" + // CHECK-NEXT: ]} + + // A failed downcast does not give more information. + if (isa(a)) + return; + + clang_analyzer_printState(); + // CHECK: "failed_casts": [ + // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "casts": [ + // CHECK-NEXT: "struct B *" + // CHECK-NEXT: ]} +} Index: clang/test/Analysis/cast-value-hierarchy-succeeds.cpp =================================================================== --- /dev/null +++ clang/test/Analysis/cast-value-hierarchy-succeeds.cpp @@ -0,0 +1,44 @@ +// RUN: %clang_analyze_cc1 \ +// RUN: -analyzer-checker=core,apiModeling.llvm.CastValue,debug.ExprInspection\ +// RUN: -verify %s 2>&1 | FileCheck %s + +// expected-no-diagnostics + +#include "Inputs/llvm.h" + +using namespace llvm; + +void clang_analyzer_printState(); + +struct A {}; // A +struct B : A {}; // `-B +struct C : B {}; // `-C +struct D : C {}; // `-D + +void test_downcast(const A *a) { + clang_analyzer_printState(); + // CHECK: "dynamic_types": null + + if (!isa(a)) + return; + + clang_analyzer_printState(); + // CHECK: "dynamic_types": [ + // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "dyn_type": "struct C", "sub_classable": true } + + if (!isa(a)) + return; + + // A succeeded cast gives more precision what is the most-derived class. + clang_analyzer_printState(); + // CHECK: "dynamic_types": [ + // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "dyn_type": "struct D", "sub_classable": true } + + if (!isa(a)) + return; + + // A succeeded upcast does not give more information. + clang_analyzer_printState(); + // CHECK: "dynamic_types": [ + // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "dyn_type": "struct D", "sub_classable": true } +} Index: clang/test/Analysis/cast-value-hierarchy.cpp =================================================================== --- /dev/null +++ clang/test/Analysis/cast-value-hierarchy.cpp @@ -0,0 +1,73 @@ +// RUN: %clang_analyze_cc1 \ +// RUN: -analyzer-checker=core,apiModeling.llvm.CastValue,debug.ExprInspection\ +// RUN: -verify %s + +#include "Inputs/llvm.h" + +using namespace llvm; + +void clang_analyzer_warnIfReached(); + // X +struct X {}; // / \. +struct Y : X {}; // Y-. \. +struct Z : X, Y {}; // `-Z +// expected-warning@-1 {{direct base 'X' is inaccessible due to ambiguity:\n struct Z -> struct X\n struct Z -> struct Y -> struct X}} + +void test_triangle_feasible(const X *x) { + if (isa(x)) + if (isa(x)) + clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}} +} + +void test_triangle_infeasible(const X *x) { + if (!isa(x)) + if (isa(x)) + clang_analyzer_warnIfReached(); // no-warning +} + +struct A {}; // A +struct B : virtual A {}; // / \. +struct C : virtual A {}; // B C +struct D : B, C {}; // \ / \. +struct E : C {}; // D E + +void test_failures_set(const A *a) { + if (isa(a) || isa(a)) + if (isa(a)) + clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}} +} + +void test_faiures_set_infeasible(const A *a) { + if (!isa(a) && isa(a)) + if (isa(a)) + clang_analyzer_warnIfReached(); // no-warning +} + +void test_downcast(const A *a) { + if (isa(a)) { + if (isa(a)) + clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}} + } +} + +// Here 'a' could be a 'D'. +void test_downcast_wonky(const A *a) { + if (isa(a)) + if (isa(a)) + clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}} +} + +void test_upcast(const A *a) { + if (isa(a) && isa(a)) { + clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}} + + if (isa(a)) + clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}} + } +} + +void test_downcast_chaining_infeasible(const A *a) { + if (isa(a) && !isa(a)) + if (isa(a) || isa(a)) + clang_analyzer_warnIfReached(); // no-warning +} Index: clang/test/Analysis/cast-value-notes.cpp =================================================================== --- clang/test/Analysis/cast-value-notes.cpp +++ clang/test/Analysis/cast-value-notes.cpp @@ -12,8 +12,8 @@ template const T *getAs() const; }; -class Triangle : public Shape {}; -class Circle : public Shape {}; +struct Triangle : Shape {}; +struct Circle : Shape {}; } // namespace clang using namespace llvm; @@ -37,12 +37,6 @@ return; } - if (dyn_cast_or_null(C)) { - // expected-note@-1 {{Assuming 'C' is not a 'Triangle'}} - // expected-note@-2 {{Taking false branch}} - return; - } - if (isa(C)) { // expected-note@-1 {{'C' is not a 'Triangle'}} // expected-note@-2 {{Taking false branch}} @@ -65,14 +59,8 @@ // expected-note@-1 {{'S' is a 'Circle'}} // expected-note@-2 {{'C' initialized here}} - if (!isa(C)) { - // expected-note@-1 {{Assuming 'C' is a 'Triangle'}} - // expected-note@-2 {{Taking false branch}} - return; - } - - if (!isa(C)) { - // expected-note@-1 {{'C' is a 'Triangle'}} + if (isa(C)) { + // expected-note@-1 {{'C' is not a 'Triangle'}} // expected-note@-2 {{Taking false branch}} return; } Index: clang/test/Analysis/cast-value-state-dump.cpp =================================================================== --- clang/test/Analysis/cast-value-state-dump.cpp +++ clang/test/Analysis/cast-value-state-dump.cpp @@ -8,22 +8,27 @@ namespace clang { struct Shape {}; -class Triangle : public Shape {}; -class Circle : public Shape {}; -class Square : public Shape {}; +struct Circle : Shape {}; +struct Square : Shape {}; +struct Octagram : Shape {}; } // namespace clang using namespace llvm; using namespace clang; void evalNonNullParamNonNullReturn(const Shape *S) { + if (isa(S)) { + // expected-note@-1 {{Assuming 'S' is not a 'Octagram'}} + // expected-note@-2 {{Taking false branch}} + return; + } + const auto *C = dyn_cast_or_null(S); // expected-note@-1 {{Assuming 'S' is a 'Circle'}} // expected-note@-2 {{'C' initialized here}} - // FIXME: We assumed that 'S' is a 'Circle' therefore it is not a 'Square'. if (dyn_cast_or_null(S)) { - // expected-note@-1 {{Assuming 'S' is not a 'Square'}} + // expected-note@-1 {{'S' is not a 'Square'}} // expected-note@-2 {{Taking false branch}} return; } @@ -31,13 +36,18 @@ clang_analyzer_printState(); // CHECK: "dynamic_types": [ - // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "dyn_type": "const class clang::Circle", "sub_classable": true } + // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "dyn_type": "const struct clang::Circle", "sub_classable": true } // CHECK-NEXT: ], - // CHECK-NEXT: "dynamic_casts": [ - // CHECK: { "region": "SymRegion{reg_$0}", "casts": [ - // CHECK-NEXT: { "from": "const struct clang::Shape *", "to": "const class clang::Circle *", "kind": "success" }, - // CHECK-NEXT: { "from": "const struct clang::Shape *", "to": "const class clang::Square *", "kind": "fail" } + // CHECK-NEXT: "succeeded_casts": [ + // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "casts": [ + // CHECK-NEXT: "const struct clang::Circle *" // CHECK-NEXT: ]} + // CHECK-NEXT: ], + // CHECK-NEXT: "failed_casts": [ + // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "casts": [ + // CHECK-NEXT: "const struct clang::Square *", "struct clang::Octagram *" + // CHECK-NEXT: ]} + // CHECK-NEXT: ], (void)(1 / !C); // expected-note@-1 {{'C' is non-null}} Index: clang/test/Analysis/expr-inspection.c =================================================================== --- clang/test/Analysis/expr-inspection.c +++ clang/test/Analysis/expr-inspection.c @@ -38,8 +38,8 @@ // CHECK-NEXT: { "symbol": "reg_$0", "range": "{ [-2147483648, 13] }" } // CHECK-NEXT: ], // CHECK-NEXT: "dynamic_types": null, -// CHECK-NEXT: "dynamic_casts": null, +// CHECK-NEXT: "succeeded_casts": null, +// CHECK-NEXT: "failed_casts": null, // CHECK-NEXT: "constructing_objects": null, // CHECK-NEXT: "checker_messages": null // CHECK-NEXT: } -