diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h @@ -52,6 +52,8 @@ iterator begin() const { return L.begin(); } iterator end() const { return L.end(); } + QualType getType() const { return T; } + static void Profile(llvm::FoldingSetNodeID& ID, QualType T, llvm::ImmutableList L); diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h @@ -201,6 +201,19 @@ SymExpr::symbol_iterator symbol_end() const { return SymExpr::symbol_end(); } + + /// Try to get a reasonable type for the given value. + /// + /// \returns The best approximation of the value type or Null. + /// In theory, all symbolic values should be typed, but this function + /// is still a WIP and might have a few blind spots. + /// + /// \note This function should not be used when the user has access to the + /// bound expression AST node as well, since AST always has exact types. + /// + /// \note Loc values are interpreted as pointer rvalues for the purposes of + /// this method. + QualType getType(const ASTContext &) const; }; inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) { diff --git a/clang/lib/StaticAnalyzer/Core/SVals.cpp b/clang/lib/StaticAnalyzer/Core/SVals.cpp --- a/clang/lib/StaticAnalyzer/Core/SVals.cpp +++ b/clang/lib/StaticAnalyzer/Core/SVals.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" +#include "clang/AST/ASTContext.h" #include "clang/AST/Decl.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/Expr.h" @@ -21,6 +22,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" #include "llvm/ADT/Optional.h" @@ -136,6 +138,63 @@ return nullptr; } +namespace { +class TypeRetrievingVisitor + : public FullSValVisitor { +private: + const ASTContext &Context; + +public: + TypeRetrievingVisitor(const ASTContext &Context) : Context(Context) {} + + QualType VisitLocMemRegionVal(loc::MemRegionVal MRV) { + return Visit(MRV.getRegion()); + } + QualType VisitLocGotoLabel(loc::GotoLabel GL) { + return QualType{Context.VoidPtrTy}; + } + template QualType VisitConcreteInt(ConcreteInt CI) { + const llvm::APSInt &Value = CI.getValue(); + return Context.getIntTypeForBitwidth(Value.getBitWidth(), Value.isSigned()); + } + QualType VisitLocConcreteInt(loc::ConcreteInt CI) { + return VisitConcreteInt(CI); + } + QualType VisitNonLocConcreteInt(nonloc::ConcreteInt CI) { + return VisitConcreteInt(CI); + } + QualType VisitNonLocLocAsInteger(nonloc::LocAsInteger LI) { + QualType NestedType = Visit(LI.getLoc()); + if (NestedType.isNull()) + return NestedType; + + return Context.getIntTypeForBitwidth(LI.getNumBits(), + NestedType->isSignedIntegerType()); + } + QualType VisitNonLocCompoundVal(nonloc::CompoundVal CV) { + return CV.getValue()->getType(); + } + QualType VisitNonLocLazyCompoundVal(nonloc::LazyCompoundVal LCV) { + return LCV.getRegion()->getValueType(); + } + QualType VisitNonLocSymbolVal(nonloc::SymbolVal SV) { + return Visit(SV.getSymbol()); + } + QualType VisitSymbolicRegion(const SymbolicRegion *SR) { + return Visit(SR->getSymbol()); + } + QualType VisitTypedRegion(const TypedRegion *TR) { + return TR->getLocationType(); + } + QualType VisitSymExpr(const SymExpr *SE) { return SE->getType(); } +}; +} // end anonymous namespace + +QualType SVal::getType(const ASTContext &Context) const { + TypeRetrievingVisitor TRV{Context}; + return TRV.Visit(*this); +} + const MemRegion *loc::MemRegionVal::stripCasts(bool StripBaseCasts) const { const MemRegion *R = getRegion(); return R ? R->StripCasts(StripBaseCasts) : nullptr; diff --git a/clang/unittests/StaticAnalyzer/CMakeLists.txt b/clang/unittests/StaticAnalyzer/CMakeLists.txt --- a/clang/unittests/StaticAnalyzer/CMakeLists.txt +++ b/clang/unittests/StaticAnalyzer/CMakeLists.txt @@ -11,8 +11,9 @@ ParamRegionTest.cpp RangeSetTest.cpp RegisterCustomCheckersTest.cpp - StoreTest.cpp + StoreTest.cpp SymbolReaperTest.cpp + SValTest.cpp TestReturnValueUnderConstruction.cpp ) diff --git a/clang/unittests/StaticAnalyzer/SValTest.cpp b/clang/unittests/StaticAnalyzer/SValTest.cpp new file mode 100644 --- /dev/null +++ b/clang/unittests/StaticAnalyzer/SValTest.cpp @@ -0,0 +1,366 @@ +//===- unittests/StaticAnalyzer/SvalTest.cpp ------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include "CheckerRegistration.h" + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclGroup.h" +#include "clang/AST/RecursiveASTVisitor.h" +#include "clang/AST/Stmt.h" +#include "clang/AST/Type.h" +#include "clang/StaticAnalyzer/Core/Checker.h" +#include "clang/StaticAnalyzer/Core/CheckerManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" +#include "clang/StaticAnalyzer/Frontend/AnalysisConsumer.h" +#include "clang/StaticAnalyzer/Frontend/CheckerRegistry.h" +#include "clang/Tooling/Tooling.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/raw_ostream.h" +#include "gtest/gtest.h" + +namespace clang { + +// getType() tests include whole bunch of type comparisons, +// so when something is wrong, it's good to have gtest telling us +// what are those types. +LLVM_ATTRIBUTE_UNUSED std::ostream &operator<<(std::ostream &OS, + const QualType &T) { + return OS << T.getAsString(); +} + +LLVM_ATTRIBUTE_UNUSED std::ostream &operator<<(std::ostream &OS, + const CanQualType &T) { + return OS << QualType{T}; +} + +namespace ento { +namespace { + +//===----------------------------------------------------------------------===// +// Testing framework implementation +//===----------------------------------------------------------------------===// + +/// A simple map from variable names to symbolic values used to init them. +using SVals = llvm::StringMap; + +/// SValCollector is the barebone of all tests. +/// +/// It is implemented as a checker and reacts to binds, so we find +/// symbolic values of interest, and to end analysis, where we actually +/// can test whatever we gathered. +class SValCollector : public Checker { +public: + void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const { + // Skip instantly if we finished testing. + // Also, we care only for binds happening in variable initializations. + if (Tested || !isa(S)) + return; + + if (const auto *VR = llvm::dyn_cast_or_null(Loc.getAsRegion())) { + CollectedSVals[VR->getDescriptiveName(false)] = Val; + } + } + + void checkEndAnalysis(ExplodedGraph &G, BugReporter &B, + ExprEngine &Engine) const { + if (!Tested) { + test(Engine, Engine.getContext()); + Tested = true; + CollectedSVals.clear(); + } + } + + /// Helper function for tests to access bound symbolic values. + SVal getByName(StringRef Name) const { return CollectedSVals[Name]; } + +private: + /// Entry point for tests. + virtual void test(ExprEngine &Engine, const ASTContext &Context) const = 0; + + mutable bool Tested = false; + mutable SVals CollectedSVals; +}; + +// SVAL_TEST is a combined way of providing a short code snippet and +// to test some programmatic predicates on symbolic values produced by the +// engine for the actual code. +// +// Each test has a NAME. One can think of it as a name for normal gtests. +// +// Each test should provide a CODE snippet. Code snippets might contain any +// valid C/C++, but have ONLY ONE defined function. There are no requirements +// about function's name or parameters. It can even be a class method. The +// body of the function must contain a set of variable declarations. Each +// variable declaration gets bound to a symbolic value, so for the following +// example: +// +// int x = ; +// +// `x` will be bound to whatever symbolic value the engine produced for . +// LIVENESS and REASSIGNMENTS don't affect this binding. +// +// During the test the actual values can be accessed via `getByName` function, +// and, for the `x`-bound value, one must use "x" as its name. +// +// Example: +// SVAL_TEST(SimpleSValTest, R"( +// void foo() { +// int x = 42; +// })") { +// SVal X = getByName("x"); +// EXPECT_TRUE(X.isConstant(42)); +// } +#define SVAL_TEST(NAME, CODE) \ + class NAME##SValCollector final : public SValCollector { \ + public: \ + void test(ExprEngine &Engine, const ASTContext &Context) const override; \ + }; \ + \ + void add##NAME##SValCollector(AnalysisASTConsumer &AnalysisConsumer, \ + AnalyzerOptions &AnOpts) { \ + AnOpts.CheckersAndPackages = {{"test.##NAME##SValCollector", true}}; \ + AnalysisConsumer.AddCheckerRegistrationFn([](CheckerRegistry &Registry) { \ + Registry.addChecker("test.##NAME##SValCollector", \ + "Description", ""); \ + }); \ + } \ + \ + TEST(SValTest, NAME) { runCheckerOnCode(CODE); } \ + void NAME##SValCollector::test(ExprEngine &Engine, \ + const ASTContext &Context) const + +//===----------------------------------------------------------------------===// +// Actual tests +//===----------------------------------------------------------------------===// + +SVAL_TEST(GetConstType, R"( +void foo() { + int x = 42; + int *y = nullptr; +})") { + SVal X = getByName("x"); + ASSERT_FALSE(X.getType(Context).isNull()); + EXPECT_EQ(Context.IntTy, X.getType(Context)); + + SVal Y = getByName("y"); + ASSERT_FALSE(Y.getType(Context).isNull()); + EXPECT_EQ(Context.getUIntPtrType(), Y.getType(Context)); +} + +SVAL_TEST(GetLocAsIntType, R"( +void foo(int *x) { + long int a = (long int)x; + unsigned b = (long unsigned)&a; + int c = (long int)nullptr; +})") { + SVal A = getByName("a"); + ASSERT_FALSE(A.getType(Context).isNull()); + // TODO: Turn it into signed long + EXPECT_EQ(Context.UnsignedLongTy, A.getType(Context)); + + SVal B = getByName("b"); + ASSERT_FALSE(B.getType(Context).isNull()); + EXPECT_EQ(Context.UnsignedIntTy, B.getType(Context)); + + SVal C = getByName("c"); + ASSERT_FALSE(C.getType(Context).isNull()); + EXPECT_EQ(Context.IntTy, C.getType(Context)); +} + +SVAL_TEST(GetSymExprType, R"( +void foo(int a, int b) { + int x = a; + int y = a + b; + long z = a; +})") { + QualType Int = Context.IntTy; + + SVal X = getByName("x"); + ASSERT_FALSE(X.getType(Context).isNull()); + EXPECT_EQ(Int, X.getType(Context)); + + SVal Y = getByName("y"); + ASSERT_FALSE(Y.getType(Context).isNull()); + EXPECT_EQ(Int, Y.getType(Context)); + + // TODO: Change to Long when we support symbolic casts + SVal Z = getByName("z"); + ASSERT_FALSE(Z.getType(Context).isNull()); + EXPECT_EQ(Int, Z.getType(Context)); +} + +SVAL_TEST(GetPointerType, R"( +int *bar(); +int &foobar(); +struct Z { + int a; + int *b; +}; +void foo(int x, int *y, Z z) { + int &a = x; + int &b = *y; + int &c = *bar(); + int &d = foobar(); + int &e = z.a; + int &f = *z.b; +})") { + QualType Int = Context.IntTy; + + SVal A = getByName("a"); + ASSERT_FALSE(A.getType(Context).isNull()); + const auto *APtrTy = dyn_cast(A.getType(Context)); + ASSERT_NE(APtrTy, nullptr); + EXPECT_EQ(Int, APtrTy->getPointeeType()); + + SVal B = getByName("b"); + ASSERT_FALSE(B.getType(Context).isNull()); + const auto *BPtrTy = dyn_cast(B.getType(Context)); + ASSERT_NE(BPtrTy, nullptr); + EXPECT_EQ(Int, BPtrTy->getPointeeType()); + + SVal C = getByName("c"); + ASSERT_FALSE(C.getType(Context).isNull()); + const auto *CPtrTy = dyn_cast(C.getType(Context)); + ASSERT_NE(CPtrTy, nullptr); + EXPECT_EQ(Int, CPtrTy->getPointeeType()); + + SVal D = getByName("d"); + ASSERT_FALSE(D.getType(Context).isNull()); + const auto *DRefTy = dyn_cast(D.getType(Context)); + ASSERT_NE(DRefTy, nullptr); + EXPECT_EQ(Int, DRefTy->getPointeeType()); + + SVal E = getByName("e"); + ASSERT_FALSE(E.getType(Context).isNull()); + const auto *EPtrTy = dyn_cast(E.getType(Context)); + ASSERT_NE(EPtrTy, nullptr); + EXPECT_EQ(Int, EPtrTy->getPointeeType()); + + SVal F = getByName("f"); + ASSERT_FALSE(F.getType(Context).isNull()); + const auto *FPtrTy = dyn_cast(F.getType(Context)); + ASSERT_NE(FPtrTy, nullptr); + EXPECT_EQ(Int, FPtrTy->getPointeeType()); +} + +SVAL_TEST(GetCompoundType, R"( +struct TestStruct { + int a, b; +}; +union TestUnion { + int a; + float b; + TestStruct c; +}; +void foo(int x) { + int a[] = {1, x, 2}; + TestStruct b = {x, 42}; + TestUnion c = {42}; + TestUnion d = {.c=b}; +} +)") { + SVal A = getByName("a"); + ASSERT_FALSE(A.getType(Context).isNull()); + const auto *AArrayType = dyn_cast(A.getType(Context)); + ASSERT_NE(AArrayType, nullptr); + EXPECT_EQ(Context.IntTy, AArrayType->getElementType()); + + SVal B = getByName("b"); + ASSERT_FALSE(B.getType(Context).isNull()); + const auto *BRecordType = dyn_cast(B.getType(Context)); + ASSERT_NE(BRecordType, nullptr); + EXPECT_EQ("TestStruct", BRecordType->getDecl()->getName()); + + SVal C = getByName("c"); + ASSERT_FALSE(C.getType(Context).isNull()); + const auto *CRecordType = dyn_cast(C.getType(Context)); + ASSERT_NE(CRecordType, nullptr); + EXPECT_EQ("TestUnion", CRecordType->getDecl()->getName()); + + auto D = getByName("d").getAs(); + ASSERT_TRUE(D.hasValue()); + auto Begin = D->begin(); + ASSERT_NE(D->end(), Begin); + ++Begin; + ASSERT_EQ(D->end(), Begin); + auto LD = D->begin()->getAs(); + ASSERT_TRUE(LD.hasValue()); + auto LDT = LD->getType(Context); + ASSERT_FALSE(LDT.isNull()); + const auto *DRecordType = dyn_cast(LDT); + ASSERT_NE(DRecordType, nullptr); + EXPECT_EQ("TestStruct", DRecordType->getDecl()->getName()); +} + +SVAL_TEST(GetStringType, R"( +void foo() { + const char *a = "Hello, world!"; +} +)") { + SVal A = getByName("a"); + ASSERT_FALSE(A.getType(Context).isNull()); + const auto *APtrTy = dyn_cast(A.getType(Context)); + ASSERT_NE(APtrTy, nullptr); + EXPECT_EQ(Context.CharTy, APtrTy->getPointeeType()); +} + +SVAL_TEST(GetThisType, R"( +class TestClass { + void foo(); +}; +void TestClass::foo() { + const auto *a = this; +} +)") { + SVal A = getByName("a"); + ASSERT_FALSE(A.getType(Context).isNull()); + const auto *APtrTy = dyn_cast(A.getType(Context)); + ASSERT_NE(APtrTy, nullptr); + const auto *ARecordType = dyn_cast(APtrTy->getPointeeType()); + ASSERT_NE(ARecordType, nullptr); + EXPECT_EQ("TestClass", ARecordType->getDecl()->getName()); +} + +SVAL_TEST(GetFunctionPtrType, R"( +void bar(); +void foo() { + auto *a = &bar; +} +)") { + SVal A = getByName("a"); + ASSERT_FALSE(A.getType(Context).isNull()); + const auto *APtrTy = dyn_cast(A.getType(Context)); + ASSERT_NE(APtrTy, nullptr); + ASSERT_TRUE(isa(APtrTy->getPointeeType())); +} + +SVAL_TEST(GetLabelType, R"( +void foo() { + entry: + void *a = &&entry; + char *b = (char *)&&entry; +} +)") { + SVal A = getByName("a"); + ASSERT_FALSE(A.getType(Context).isNull()); + EXPECT_EQ(Context.VoidPtrTy, A.getType(Context)); + + SVal B = getByName("a"); + ASSERT_FALSE(B.getType(Context).isNull()); + // TODO: Change to CharTy when we support symbolic casts + EXPECT_EQ(Context.VoidPtrTy, B.getType(Context)); +} + +} // namespace +} // namespace ento +} // namespace clang