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" @@ -29,33 +28,40 @@ namespace clang { namespace ento { +/// See whether the record of type \p X is derived from the record of type \p Y. +bool isDerivedFrom(QualType X, QualType Y); + /// Get dynamic type information for the region \p MR. -DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR); +const DynamicTypeInfo *getDynamicTypeInfo(ProgramStateRef State, + const MemRegion *MR); -/// Get raw dynamic type information for the region \p MR. -const DynamicTypeInfo *getRawDynamicTypeInfo(ProgramStateRef State, - const MemRegion *MR); +/// Get the stored dynamic type information for the region \p MR. +const DynamicTypeInfo *getStoredDynamicTypeInfo(ProgramStateRef State, + const MemRegion *MR); -/// Get dynamic cast information from \p CastFromTy to \p CastToTy of \p MR. -const DynamicCastInfo *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 on \p MR. +const DynamicTypeInfo *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, - DynamicTypeInfo NewTy); + const DynamicTypeInfo *NewTy); /// Set dynamic type information of the region; return the new state. ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, QualType NewTy, bool CanBeSubClassed = true); /// Set dynamic type and cast information of the region; return the new state. +/// 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. ProgramStateRef setDynamicTypeAndCastInfo(ProgramStateRef State, const MemRegion *MR, - QualType CastFromTy, QualType CastToTy, - bool IsCastSucceeds); + const DynamicTypeInfo *CastInfo, + bool CastSucceeds); /// 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 /// 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,103 @@ }; } // namespace -static bool isInfeasibleCast(const DynamicCastInfo *CastInfo, - bool CastSucceeds) { - if (!CastInfo) +// See 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. +static bool isOneEqualOrDerivedFromOther(QualType X, QualType Y) { + if (X->getPointeeCXXRecordDecl() == Y->getPointeeCXXRecordDecl()) + return true; + + return isDerivedFrom(X, Y) || isDerivedFrom(Y, X); +} + +// 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 there exists at least one directed path either from +// 'X' to 'Y' or from 'Y' to 'X' in the inheritance. +// 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'. +// +// 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): 'S(r) <-> Y'. +// +// 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 bool isSuccededCast(const DynamicTypeInfo *SucceededCastInfo, + const DynamicTypeInfo *FailedCastInfo, + QualType CastFromTy, QualType CastToTy) { + if (FailedCastInfo || !isOneEqualOrDerivedFromOther(CastFromTy, CastToTy)) return false; - return CastSucceeds ? CastInfo->fails() : CastInfo->succeeds(); + if (!SucceededCastInfo) + return true; + + return isOneEqualOrDerivedFromOther(SucceededCastInfo->getType(), CastToTy); } -static const NoteTag *getNoteTag(CheckerContext &C, - const DynamicCastInfo *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) { + const DynamicTypeInfo *SucceededCastInfo = + getStoredDynamicTypeInfo(State, MR); + + const DynamicTypeInfo *FailedCastInfo = + getFailedCastInfo(State, MR, CastToTy); + + // We assume that every checked cast succeeds. + bool IsAlwaysSucceeds = + IsCheckedCast || CastFromTy->getPointeeCXXRecordDecl() == + CastToTy->getPointeeCXXRecordDecl(); + + CastSucceeds = + IsAlwaysSucceeds || + (Assumption && isSuccededCast(SucceededCastInfo, FailedCastInfo, + CastFromTy, CastToTy)); + + IsKnownCast = IsAlwaysSucceeds || SucceededCastInfo || + (!CastSucceeds && FailedCastInfo); + + CastInfo = CastSucceeds ? SucceededCastInfo : FailedCastInfo; + } + + bool IsKnownCast, CastSucceeds; + const DynamicTypeInfo *CastInfo; +}; +} // namespace + +constexpr llvm::StringLiteral Vowels = "aeiou"; + +static const NoteTag *getNoteTag(CheckerContext &C, const Expr *Object, + QualType CastToTy, CastContext &CastCtx) { + QualType KnownCastToTy; + if (CastCtx.CastInfo) + 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 +190,25 @@ 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 ") + << (Vowels.contains_lower(CastToName[0]) ? "an" : "a") << " '" + << CastToName << '\''; return Out.str(); }, - /*IsPrunable=*/true); + /*IsPrunable=*/!CastCtx.CastSucceeds); } //===----------------------------------------------------------------------===// @@ -157,8 +234,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 +261,19 @@ } const MemRegion *MR = DV.getAsRegion(); - const DynamicCastInfo *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 = setDynamicTypeAndCastInfo(State, MR, CastToTy, CastCtx.CastInfo, + CastCtx.CastSucceeds); - // 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, @@ -220,6 +283,7 @@ const FunctionDecl *FD = Call.getDecl()->getAsFunction(); QualType CastFromTy = Call.parameters()[0]->getType(); QualType CastToTy = FD->getTemplateSpecializationArgs()->get(0).getAsType(); + if (CastFromTy->isPointerType()) CastToTy = C.getASTContext().getPointerType(CastToTy); else if (CastFromTy->isReferenceType()) @@ -228,31 +292,16 @@ return; const MemRegion *MR = DV.getAsRegion(); - const DynamicCastInfo *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 = setDynamicTypeAndCastInfo(State, MR, CastToTy, CastCtx.CastInfo, + CastCtx.CastSucceeds); 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 +447,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/Checkers/DynamicTypeChecker.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/DynamicTypeChecker.cpp +++ clang/lib/StaticAnalyzer/Checkers/DynamicTypeChecker.cpp @@ -93,13 +93,12 @@ ProgramStateRef State = N->getState(); ProgramStateRef StatePrev = N->getFirstPred()->getState(); - DynamicTypeInfo TrackedType = getDynamicTypeInfo(State, Reg); - DynamicTypeInfo TrackedTypePrev = getDynamicTypeInfo(StatePrev, Reg); - if (!TrackedType.isValid()) + const DynamicTypeInfo *TrackedType = getDynamicTypeInfo(State, Reg); + const DynamicTypeInfo *TrackedTypePrev = getDynamicTypeInfo(StatePrev, Reg); + if (!TrackedType) return nullptr; - if (TrackedTypePrev.isValid() && - TrackedTypePrev.getType() == TrackedType.getType()) + if (TrackedTypePrev && TrackedTypePrev->getType() == TrackedType->getType()) return nullptr; // Retrieve the associated statement. @@ -112,7 +111,7 @@ SmallString<256> Buf; llvm::raw_svector_ostream OS(Buf); OS << "Type '"; - QualType::print(TrackedType.getType().getTypePtr(), Qualifiers(), OS, + QualType::print(TrackedType->getType().getTypePtr(), Qualifiers(), OS, LangOpts, llvm::Twine()); OS << "' is inferred from "; @@ -163,12 +162,11 @@ return; ProgramStateRef State = C.getState(); - DynamicTypeInfo DynTypeInfo = getDynamicTypeInfo(State, Region); - - if (!DynTypeInfo.isValid()) + const DynamicTypeInfo *DynTypeInfo = getDynamicTypeInfo(State, Region); + if (!DynTypeInfo) return; - QualType DynType = DynTypeInfo.getType(); + QualType DynType = DynTypeInfo->getType(); QualType StaticType = CE->getType(); const auto *DynObjCType = DynType->getAs(); @@ -193,7 +191,7 @@ if (ASTCtxt.canAssignObjCInterfaces(StaticObjCType, DynObjCType)) return; - if (DynTypeInfo.canBeASubClass() && + if (DynTypeInfo->canBeASubClass() && ASTCtxt.canAssignObjCInterfaces(DynObjCType, StaticObjCType)) return; Index: clang/lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp +++ clang/lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp @@ -224,7 +224,7 @@ const MemRegion *RecReg = Msg->getReceiverSVal().getAsRegion(); if (!RecReg) return; - DynamicTypeInfo RecDynType = getDynamicTypeInfo(State, RecReg); + const DynamicTypeInfo *RecDynType = getDynamicTypeInfo(State, RecReg); C.addTransition(setDynamicTypeInfo(State, RetReg, RecDynType)); break; } @@ -351,10 +351,15 @@ CastE->getType()->getAs(); if (!NewTy) return nullptr; - QualType OldDTy = getDynamicTypeInfo(C.getState(), ToR).getType(); + + QualType OldDTy; + if (const DynamicTypeInfo *DTI = getDynamicTypeInfo(C.getState(), ToR)) + OldDTy = DTI->getType(); + if (OldDTy.isNull()) { return NewTy; } + const ObjCObjectPointerType *OldTy = OldDTy->getAs(); if (!OldTy) @@ -875,7 +880,7 @@ // When there is an entry available for the return symbol in DynamicTypeMap, // the call was inlined, and the information in the DynamicTypeMap is should // be precise. - if (RetRegion && !getRawDynamicTypeInfo(State, RetRegion)) { + if (RetRegion && !getStoredDynamicTypeInfo(State, RetRegion)) { // TODO: we have duplicated information in DynamicTypeMap and // MostSpecializedTypeArgsMap. We should only store anything in the later if // the stored data differs from the one stored in the former. Index: clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -1909,10 +1909,10 @@ const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, const MemRegion *Reg) { auto TI = getDynamicTypeInfo(State, Reg); - if (!TI.isValid()) + if (!TI) return nullptr; - auto Type = TI.getType(); + auto Type = TI->getType(); if (const auto *RefT = Type->getAs()) { Type = RefT->getPointeeType(); } Index: clang/lib/StaticAnalyzer/Core/CallEvent.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/CallEvent.cpp +++ clang/lib/StaticAnalyzer/Core/CallEvent.cpp @@ -735,12 +735,12 @@ return {}; // Do we know anything about the type of 'this'? - DynamicTypeInfo DynType = getDynamicTypeInfo(getState(), R); - if (!DynType.isValid()) + const DynamicTypeInfo *DynType = getDynamicTypeInfo(getState(), R); + if (!DynType) return {}; // Is the type a C++ class? (This is mostly a defensive check.) - QualType RegionType = DynType.getType()->getPointeeType(); + QualType RegionType = DynType->getType()->getPointeeType(); assert(!RegionType.isNull() && "DynamicTypeInfo should always be a pointer."); const CXXRecordDecl *RD = RegionType->getAsCXXRecordDecl(); @@ -769,7 +769,7 @@ // Does the decl that we found have an implementation? const FunctionDecl *Definition; if (!Result->hasBody(Definition)) { - if (!DynType.canBeASubClass()) + if (!DynType->canBeASubClass()) return AnyFunctionCall::getRuntimeDefinition(); return {}; } @@ -777,7 +777,7 @@ // We found a definition. If we're not sure that this devirtualization is // actually what will happen at runtime, make sure to provide the region so // that ExprEngine can decide what to do with it. - if (DynType.canBeASubClass()) + if (DynType->canBeASubClass()) return RuntimeDefinition(Definition, R->StripCasts()); return RuntimeDefinition(Definition, /*DispatchRegion=*/nullptr); } @@ -1206,15 +1206,15 @@ if (!Receiver) return {}; - DynamicTypeInfo DTI = getDynamicTypeInfo(getState(), Receiver); - if (!DTI.isValid()) { + const DynamicTypeInfo *DTI = getDynamicTypeInfo(getState(), Receiver); + if (!DTI) { assert(isa(Receiver) && "Unhandled untyped region class!"); return {}; } - QualType DynType = DTI.getType(); - CanBeSubClassed = DTI.canBeASubClass(); + QualType DynType = DTI->getType(); + CanBeSubClassed = DTI->canBeASubClass(); ReceiverT = dyn_cast(DynType.getCanonicalType()); if (ReceiverT && CanBeSubClassed) Index: clang/lib/StaticAnalyzer/Core/DynamicType.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/DynamicType.cpp +++ clang/lib/StaticAnalyzer/Core/DynamicType.cpp @@ -27,92 +27,126 @@ 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 failed cast informations. +REGISTER_MAP_WITH_PROGRAMSTATE(FailedCastMap, const clang::ento::MemRegion *, CastSet) namespace clang { namespace ento { -DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR) { - MR = MR->StripCasts(); +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(); + return XRD == YRD || XRD->isDerivedFrom(YRD); +} + +const DynamicTypeInfo *getDynamicTypeInfo(ProgramStateRef State, + const MemRegion *MR) { + MR = getSimplifiedRegion(MR); // Look up the dynamic type in the GDM. if (const DynamicTypeInfo *DTI = State->get(MR)) - return *DTI; + return DTI; // Otherwise, fall back to what we know about the region. if (const auto *TR = dyn_cast(MR)) - return DynamicTypeInfo(TR->getLocationType(), /*CanBeSub=*/false); + return new DynamicTypeInfo(TR->getLocationType(), /*CanBeSub=*/false); - if (const auto *SR = dyn_cast(MR)) { - SymbolRef Sym = SR->getSymbol(); - return DynamicTypeInfo(Sym->getType()); - } + if (const auto *SR = dyn_cast(MR)) + return new DynamicTypeInfo(SR->getSymbol()->getType()); - return {}; + return nullptr; } -const DynamicTypeInfo *getRawDynamicTypeInfo(ProgramStateRef State, - const MemRegion *MR) { +const DynamicTypeInfo *getStoredDynamicTypeInfo(ProgramStateRef State, + const MemRegion *MR) { + if (!MR) + return nullptr; + + MR = getSimplifiedRegion(MR); return State->get(MR); } -const DynamicCastInfo *getDynamicCastInfo(ProgramStateRef State, - const MemRegion *MR, - QualType CastFromTy, - QualType CastToTy) { - const auto *Lookup = State->get().lookup(MR); +const DynamicTypeInfo *getFailedCastInfo(ProgramStateRef State, + const MemRegion *MR, + QualType CastToTy) { + if (!MR) + return nullptr; + + MR = getSimplifiedRegion(MR); + const auto *Lookup = State->get().lookup(MR); if (!Lookup) return nullptr; - 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 nullptr; } ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, - DynamicTypeInfo NewTy) { - State = State->set(MR->StripCasts(), NewTy); + const DynamicTypeInfo *NewTy) { + assert((NewTy->getType()->isAnyPointerType() || + NewTy->getType()->isReferenceType()) && + "DynamicTypeInfo should always be a pointer."); + MR = getSimplifiedRegion(MR); + State = State->set(MR, *NewTy); assert(State); return State; } ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, QualType NewTy, bool CanBeSubClassed) { - return setDynamicTypeInfo(State, MR, DynamicTypeInfo(NewTy, CanBeSubClassed)); + return setDynamicTypeInfo(State, MR, + new DynamicTypeInfo(NewTy, CanBeSubClassed)); } ProgramStateRef setDynamicTypeAndCastInfo(ProgramStateRef State, const MemRegion *MR, - QualType CastFromTy, QualType CastToTy, + const DynamicTypeInfo *CastInfo, bool CastSucceeds) { 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 = State->get(MR); - CastSet Set = TempSet ? *TempSet : F.getEmptySet(); + 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 { + CastSet::Factory &F = State->get_context(); + + const CastSet *TempSet = State->get(MR); + CastSet Set = TempSet ? *TempSet : F.getEmptySet(); + + // If there is no 'CastInfo' or the 'CastToTy' is an upcast store it. + // Upcast gives more precision what is the largest set the class cannot be. + if (CastInfo && isDerivedFrom(CastInfo->getType(), CastToTy)) { + Set = F.add(Set, CastToTy); + Set = F.remove(Set, *CastInfo); + } else if (!CastInfo || !isDerivedFrom(CastToTy, CastInfo->getType())) { + Set = F.add(Set, CastToTy); + } - Set = F.add(Set, {CastFromTy, CastToTy, ResultKind}); - State = State->set(MR, Set); + State = State->set(MR, Set); + } assert(State); return State; @@ -123,7 +157,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; } @@ -133,7 +167,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, @@ -154,7 +188,7 @@ const DynamicTypeInfo &DTI = I->second; Indent(Out, Space, IsDot) << "{ \"region\": \"" << MR << "\", \"dyn_type\": "; - if (!DTI.isValid()) { + if (DTI.getType().isNull()) { Out << "null"; } else { Out << '\"' << DTI.getType()->getPointeeType().getAsString() @@ -175,9 +209,9 @@ static void printDynamicCastsJson(raw_ostream &Out, ProgramStateRef State, const char *NL, unsigned int Space, bool IsDot) { - Indent(Out, Space, IsDot) << "\"dynamic_casts\": "; + Indent(Out, Space, IsDot) << "\"failed_casts\": "; - const DynamicCastMapTy &Map = State->get(); + const FailedCastMapTy &Map = State->get(); if (Map.isEmpty()) { Out << "null," << NL; return; @@ -185,7 +219,7 @@ ++Space; Out << '[' << NL; - for (DynamicCastMapTy::iterator I = Map.begin(); I != Map.end(); ++I) { + for (FailedCastMapTy::iterator I = Map.begin(); I != Map.end(); ++I) { const MemRegion *MR = I->first; const CastSet &Set = I->second; @@ -195,16 +229,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) << ']'; } 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,72 @@ +// 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 : A {}; // / \. +struct C : 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}} + } +} + +void test_downcast_infeasible(const A *a) { + if (isa(a)) + if (isa(a)) + clang_analyzer_warnIfReached(); // no-warning +} + +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 @@ -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 @@ -11,19 +11,31 @@ class Triangle : public Shape {}; class Circle : public Shape {}; class Square : public Shape {}; +class Octagram : public 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 'Triangle'}} + // expected-note@-2 {{Taking false branch}} + return; + } + + if (isa(S)) { + // expected-note@-1 {{Assuming 'S' is not an '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; } @@ -33,11 +45,11 @@ // CHECK: "dynamic_types": [ // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "dyn_type": "const class 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: "failed_casts": [ + // CHECK-NEXT: { "region": "SymRegion{reg_$0}", "casts": [ + // CHECK-NEXT: "const class clang::Square *", "class clang::Triangle *", "class 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,7 +38,7 @@ // CHECK-NEXT: { "symbol": "reg_$0", "range": "{ [-2147483648, 13] }" } // CHECK-NEXT: ], // CHECK-NEXT: "dynamic_types": null, -// CHECK-NEXT: "dynamic_casts": null, +// CHECK-NEXT: "failed_casts": null, // CHECK-NEXT: "constructing_objects": null, // CHECK-NEXT: "checker_messages": null // CHECK-NEXT: }