[analyzer] Implement getType for SVal

[vsavchenko]

Summary

This commit adds a function to the top-class of SVal hierarchy to
provide type information about the value. That can be extremely
useful when this is the only piece of information that the user is
actually caring about.

Additionally, this commit introduces a testing framework for writing
unit-tests for symbolic values.

[vsavchenko]

Hey folks!

I was thinking that this method can be quite handy.
I think it would be great to have another pair of eyes (but more would be better) to look into this and:

• Suggest other test cases to add
• See if I missed any "typed" values from the hierarchy
• See if getType for supported types does make sense

In particular, it would be great to hear your thoughts on SymolicRegion because it's not that obvious that we should return that type or not. On one hand, this is the best we've got, on the other hand, it can be misleading.

[NoQ]

Excellent! This utility is the first step on a lot of paths such as:

• Asserting that all expressions' values are of the right type. I expect this to uncover a lot of ridiculous mutually cancelling bugs.
• Modeling extents of RegionStore bindings - they're simply widths of their respective types.

In D104550#2827456, @vsavchenko wrote:

• See if I missed any "typed" values from the hierarchy

All values in the hierarchy are typed. Well, ideally.

See inlined comment for ConcreteInts.

One particularly important one is nonloc::LocAsInteger (And, well, why doesn't it still have signedness? - I had a patch for it like 6 years ago. Why am I so bad at committing patches?).

I think you can also easily support pointers-to-members and hopefully goto labels.

• See if getType for supported types does make sense

In particular, it would be great to hear your thoughts on SymolicRegion because it's not that obvious that we should return that type or not. On one hand, this is the best we've got, on the other hand, it can be misleading.

The type of the object it points to is indeed technically unknown. The type of the pointer represented by a loc::MemRegionVal(SymbolicRegion) is unambiguous and coincides with the type of the symbol.

In particular, if the symbol is of type void *, then it represents a void pointer value, which doesn't mean that its pointee is a void.

clang/lib/StaticAnalyzer/Core/SVals.cpp

151

This is correct except you need to get the value type, not the pointer type.

LazyCompoundVal is a prvalue and its parent region is the location in which this prvalue resided some time in the past. So the parent region is of the right type and it's always typed but you need the pointee type.

162

The biggest disappointment here is that this case is technically incorrect for the very basic case of integral types.

Because we drop casts, a symbol of an integral type may technically represent a value of a completely different integral type, the same symbol may represent multiple different values of different integral types, and so on.

This is what ruins the dream of modeling Region Store binding extents as value widths: for the single most important case we'd be getting incorrect answers.

clang/unittests/StaticAnalyzer/SValTest.cpp

145

nonloc::ConcreteInt is basically an APSInt. You can extract bit width and signedness and feed it to ASTContext::getIntTypeForBitwidth().

loc::ConcreteInt is always of the pointer type. Unless, of course, you have a target architecture with pointers of different widths, then whelp we aren't quite there yet. But when we get there, I guess it's still APSInt under the hood so a similar trick could be used.

[vsavchenko]

Support GotoLabel

[vsavchenko]

Support ConcreteInt, LocAsInteger, and GotoLabel

[vsavchenko]

clang/lib/StaticAnalyzer/Core/SVals.cpp

151

OK then, can you maybe hint how can I write a test where this is going to be a pointer type (or maybe then getType for regions works incorrectly).

162

I hope that the introduction of symbolic casts is around the corner.

clang/unittests/StaticAnalyzer/SValTest.cpp

145

OK, I guess having ASTContext as a parameter is the best choice we can have here and not such a high price to pay.

[NoQ]

clang/lib/StaticAnalyzer/Core/SVals.cpp

151

Regions have getLocationType() (the pointer type) and getValueType() (the pointee type). I think you need to call the latter directly in this case, bypassing recursion.

In order to obtain a live LazyCompoundVal specimen for testing purposes, you need to load an entire compound object (not necessarily represented by a CompoundVal) from Region Store.

Eg.,

struct MyStruct a;
// ...
struct MyStruct b = a; // Avoid C++ though, constructors are a different beast.

Or you could construct one directly. But that, of course, wouldn't give you any hints about the appropriate type.

maybe then getType for regions works incorrectly

Hmm that's actually a good separate question. How do you know if a region represents a prvalue of pointer type or a glvalue of pointee type (including, but not limited to, references)? This can't be figured out without more context just by looking at the SVal.

[vsavchenko]

clang/lib/StaticAnalyzer/Core/SVals.cpp

151

In order to obtain a live LazyCompoundVal specimen for testing purposes.

That's not a problem:

TestUnion d = {.c=b};

does produce LazyCompundVal and we don't get a pointer, but the value type. That's why I was asking how I can construct an example when this current implementation fails.

Hmm that's actually a good separate question. How do you know if a region represents a prvalue of pointer type or a glvalue of pointee type (including, but not limited to, references)? This can't be figured out without more context just by looking at the SVal.

Value categories are orthogonal to types, so I don't see why we should care for those in getType. How do you think it should affect this particular functionality?

[NoQ]

clang/lib/StaticAnalyzer/Core/SVals.cpp

151

TestUnion d = {.c=b};

(lldb) p D.dump()
compoundVal{ lazyCompoundVal{0x1110b3950,temp_object{struct TestStruct, S1276}}}

It's an eager compound value that contains a lazy compound value as the initializer for field .c.

You're still testing an eager compound value. You never visit the lazy compound value recursively.

MemRegion::getLocationType() is always a pointer type.

Value categories are orthogonal to types, so I don't see why we should care for those in getType. How do you think it should affect this particular functionality?

The static analyzer basically models operators * and & as no-op but from the perspective of the standard's formalism they jump across objects.

For example, a load from parameter int *p would produce a value &SymRegion{reg_$0<p>} that represents both the rvalue of p (which has the type int *) and the lvalue of *p (which is an entirely different object of type int).

[Szelethus]

This is not an urgent, but still a very important issue: SVal is likely among the first things a new developer in the analyzer sees. Its common around the university here that some students barely halfway through their BSc are given smaller tasks, like the implementation of a checker in the static analyzer. Instead of

// Try to get a reasonable type for the given value.

Maybe we should tell why this might fail, why its not just a type but a best effort, etc.

Despite being in the analyzer for so long, I don't have anything anything meaningful to add just yet :)

[vsavchenko]

In D104550#2832983, @Szelethus wrote:

This is not an urgent, but still a very important issue: SVal is likely among the first things a new developer in the analyzer sees. Its common around the university here that some students barely halfway through their BSc are given smaller tasks, like the implementation of a checker in the static analyzer. Instead of

// Try to get a reasonable type for the given value.

Maybe we should tell why this might fail, why its not just a type but a best effort, etc.

Despite being in the analyzer for so long, I don't have anything anything meaningful to add just yet :)

That's a good point! I guess the main obstacle for a meaningful description of "why this might fail" is what @NoQ mentioned: "all values are supposed to be typed". But if we go that deep in one commit (even doing it for a rather simple pointer-to-member case is not so small of a change), we won't get this feature at all. Do you think that "for the sake of incremental approach"-like comment can help?

[Szelethus]

In D104550#2833020, @vsavchenko wrote:

Do you think that "for the sake of incremental approach"-like comment can help?

A TODO: should be good enough for now. I see this is still a moving target.

[NoQ]

Another thing to mention about SVal::getType() in its doxygen comment is that most of the time you don't need it. Similarly to how checking whether an SVal is a Loc or a NonLoc results in incorrect code 95% of the time (because such code is unable to discriminate between arbitrary lvalues and pointer rvalues which is typically crucial in order to get everything right but often forgotten / misunderstood), relying on the type of the SVal rather than its storage raises similar problems.

The use case in RegionStore that I mentioned in the beginning is the rare exception to this rule of thumb because there's no AST expressions to tell us the type of the storage and on top of that type punning makes the storage basically entirely untyped. There's really no other way to obtain such information. Bytes in memory really don't have a type; it's very much a matter of convenient abstraction for us to associate type with them.

[ASDenysPetrov]

I'm in favor of this patch. It will help simplify SValBuilder::evalCast, which takes an optional parameter OriginalTy and acts differently based on whether it has been passed or has not.

Since sizeof(SVal) became bigger (x1.5). I'm wondering of how much this reflects on memory consumption.

Another thing is that we can garantee returning QualType. I mean, we can replace Optional with QualType itself. QualType has a default ctor and isNull predicate, which is true when defaultly constructed.

clang/lib/StaticAnalyzer/Core/SVals.cpp

153

I'm not sure this is a correct type. I would expect here something like: class LabelType : public Type.

clang/unittests/StaticAnalyzer/SValTest.cpp

182–183

Add a cast case.

191–193

[vsavchenko]

In D104550#2838827, @ASDenysPetrov wrote:

I'm in favor of this patch. It will help simplify SValBuilder::evalCast, which takes an optional parameter OriginalTy and acts differently based on whether it has been passed or has not.

@NoQ mentioned it before that it is always better to use direct types from AST. But the only participant who doesn't have AST is the Store, and when it calls evalCast it doesn't have a way to get that type. So, in this case this function van be pretty useful.

Since sizeof(SVal) became bigger (x1.5). I'm wondering of how much this reflects on memory consumption.

I'm not sure what you mean here. If it is about this particular patch, it simply adds a non-virtual method to SVal, it shouldn't affect sizeof(SVal) at all.

Another thing is that we can garantee returning QualType. I mean, we can replace Optional with QualType itself. QualType has a default ctor and isNull predicate, which is true when defaultly constructed.

I wanted to be more explicit here and convey to the user that the lack of type is normal. I can change that, it won't be a problem at all. @NoQ, @Szelethus what do you think?

clang/lib/StaticAnalyzer/Core/SVals.cpp

153

I don't think that I fully understood what you suggest here. Do you suggest to add a new type to Type.h?

clang/unittests/StaticAnalyzer/SValTest.cpp

182–183

Sure!

[Szelethus]

In D104550#2838845, @vsavchenko wrote:

Another thing is that we can garantee returning QualType. I mean, we can replace Optional with QualType itself. QualType has a default ctor and isNull predicate, which is true when defaultly constructed.

I wanted to be more explicit here and convey to the user that the lack of type is normal. I can change that, it won't be a problem at all. @NoQ, @Szelethus what do you think?

// May return nullptr.

And its all good!

In D104550#2835398, @NoQ wrote:

Another thing to mention about SVal::getType() in its doxygen comment is that most of the time you don't need it. Similarly to how checking whether an SVal is a Loc or a NonLoc results in incorrect code 95% of the time (because such code is unable to discriminate between arbitrary lvalues and pointer rvalues which is typically crucial in order to get everything right but often forgotten / misunderstood), relying on the type of the SVal rather than its storage raises similar problems.

Then I especially can't imagine a more important doxygen comment then this! We could even consider adding your point about Locs and NonLocs to SVal::getAs. The target audience are new to clang, static analysis, and C++ itself. I recall you had to beat some of this stuff into me for weeks when I implemented pointer chasing in UninitializedObjectChecker :)

[ASDenysPetrov]

I'm not sure what you mean here. If it is about this particular patch, it simply adds a non-virtual method to SVal, it shouldn't affect sizeof(SVal) at all.

My fault. For some reason I thought you added a QualType as a member to SVal declaration.

I wanted to be more explicit here and convey to the user that the lack of type is normal.

We need to think about what real usage would look and feel better.

My another proposition is to think about how we can rework ConcreteInt to Int which can keep ranges. Previosly we couldn't keep range sets inside Sval as they were ImmutableSets, but now they are just pointers to vectors. So we can pass the range set inside SVal. IMO now RangeConstraintManager is smart enough to do standart arithmetics with ranges as we do for concrete ints. These are just my recent thoughts out loud.

clang/lib/StaticAnalyzer/Core/SVals.cpp

153

Yes. As a user I expect to see some special type for labels, not a void*. But for the absence of such type let it be as is.

[NoQ]

clang/lib/StaticAnalyzer/Core/SVals.cpp

153

void * is the correct type for label values, as defined in the documentation of the respective GNU extension to C (which Clang mimics/supports):

https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html

You can get the address of a label defined in the current function (or a containing function) with the unary operator '&&'. The value has type void *.

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Core/SVals.cpp

153

OK, I see. As a MSVC user I never met this feature neither in a real code nor in the Standard. I've just checked the feature in Godbolt and MSVC is almost the only one which doesn't support it.
I'm OK with void*, since a user has additional information that this also is a GotoLabel to handle whatever way it want.

[vsavchenko]

Address comments from review

[NoQ]

Amazing, thanks!!

clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h

213

I'm also in favor of a note that says "Loc values are interpreted as pointer rvalues for the purposes of this method" or something like that.

[Szelethus]

Really appreciate the unit tests!

[vsavchenko]

Add one more note to getType docstring

[DavidSpickett]

@vsavchenko One of the added tests is failing on our 32 bit Armv7 Thumb bot: https://lab.llvm.org/buildbot/#/builders/170/builds/61

/home/tcwg-buildslave/worker/clang-thumbv7-full-2stage/llvm/clang/unittests/StaticAnalyzer/SValTest.cpp:169: Failure
Expected equality of these values:
  Context.UnsignedLongTy
    Which is: unsigned long
  A.getType(Context)
    Which is: unsigned int
[  FAILED  ] SValTest.GetLocAsIntType (22 ms)
[----------] 1 test from SValTest (22 ms total)

A 32/64 bit issue?

[vsavchenko]

In D104550#2849561, @DavidSpickett wrote:

@vsavchenko One of the added tests is failing on our 32 bit Armv7 Thumb bot: https://lab.llvm.org/buildbot/#/builders/170/builds/61

/home/tcwg-buildslave/worker/clang-thumbv7-full-2stage/llvm/clang/unittests/StaticAnalyzer/SValTest.cpp:169: Failure
Expected equality of these values:
  Context.UnsignedLongTy
    Which is: unsigned long
  A.getType(Context)
    Which is: unsigned int
[  FAILED  ] SValTest.GetLocAsIntType (22 ms)
[----------] 1 test from SValTest (22 ms total)

A 32/64 bit issue?

Hi @DavidSpickett , thanks for looking into this!
This patch was almost instantly followed by https://github.com/llvm/llvm-project/commit/b2842298cebf420ecb3750bf309021a7f37870c1 which fixed the issue. Please, let me know, if you still see it after that commit!

[DavidSpickett]

Cool. If you see a few more emails with the same thing ignore them, the armv7 bots are rather slow to catch up.

[stevewan]

In D104550#2849582, @vsavchenko wrote:

In D104550#2849561, @DavidSpickett wrote:

@vsavchenko One of the added tests is failing on our 32 bit Armv7 Thumb bot: https://lab.llvm.org/buildbot/#/builders/170/builds/61

/home/tcwg-buildslave/worker/clang-thumbv7-full-2stage/llvm/clang/unittests/StaticAnalyzer/SValTest.cpp:169: Failure
Expected equality of these values:
  Context.UnsignedLongTy
    Which is: unsigned long
  A.getType(Context)
    Which is: unsigned int
[  FAILED  ] SValTest.GetLocAsIntType (22 ms)
[----------] 1 test from SValTest (22 ms total)

A 32/64 bit issue?

Hi @DavidSpickett , thanks for looking into this!
This patch was almost instantly followed by https://github.com/llvm/llvm-project/commit/b2842298cebf420ecb3750bf309021a7f37870c1 which fixed the issue. Please, let me know, if you still see it after that commit!

Sorry for posting to this slightly aged thread. I'm seeing a similar error of this on 32 bit AIX PPC, where getUIntPtrType() returns unsigned long, so the aforementioned follow-on patch no longer applies. The results from getIntTypeForBitwidth() seem unreliable in certain cases (e.g. int vs long in ILP32), and I couldn't think of a good way around it. Have you had any future plans on mitigating such problems?

[martong]

In D104550#3139239, @stevewan wrote:

In D104550#2849582, @vsavchenko wrote:

In D104550#2849561, @DavidSpickett wrote:

@vsavchenko One of the added tests is failing on our 32 bit Armv7 Thumb bot: https://lab.llvm.org/buildbot/#/builders/170/builds/61

/home/tcwg-buildslave/worker/clang-thumbv7-full-2stage/llvm/clang/unittests/StaticAnalyzer/SValTest.cpp:169: Failure
Expected equality of these values:
  Context.UnsignedLongTy
    Which is: unsigned long
  A.getType(Context)
    Which is: unsigned int
[  FAILED  ] SValTest.GetLocAsIntType (22 ms)
[----------] 1 test from SValTest (22 ms total)

A 32/64 bit issue?

Hi @DavidSpickett , thanks for looking into this!
This patch was almost instantly followed by https://github.com/llvm/llvm-project/commit/b2842298cebf420ecb3750bf309021a7f37870c1 which fixed the issue. Please, let me know, if you still see it after that commit!

Sorry for posting to this slightly aged thread. I'm seeing a similar error of this on 32 bit AIX PPC, where getUIntPtrType() returns unsigned long, so the aforementioned follow-on patch no longer applies. The results from getIntTypeForBitwidth() seem unreliable in certain cases (e.g. int vs long in ILP32), and I couldn't think of a good way around it. Have you had any future plans on mitigating such problems?

Hi there, what is the exact target triple?
I wonder if it would be possible to create a new unit test case where we pass somehow the target triple to runCheckerOnCode?

[stevewan]

In D104550#3139684, @martong wrote:

In D104550#3139239, @stevewan wrote:

In D104550#2849582, @vsavchenko wrote:

In D104550#2849561, @DavidSpickett wrote:

@vsavchenko One of the added tests is failing on our 32 bit Armv7 Thumb bot: https://lab.llvm.org/buildbot/#/builders/170/builds/61

/home/tcwg-buildslave/worker/clang-thumbv7-full-2stage/llvm/clang/unittests/StaticAnalyzer/SValTest.cpp:169: Failure
Expected equality of these values:
  Context.UnsignedLongTy
    Which is: unsigned long
  A.getType(Context)
    Which is: unsigned int
[  FAILED  ] SValTest.GetLocAsIntType (22 ms)
[----------] 1 test from SValTest (22 ms total)

A 32/64 bit issue?

Hi @DavidSpickett , thanks for looking into this!
This patch was almost instantly followed by https://github.com/llvm/llvm-project/commit/b2842298cebf420ecb3750bf309021a7f37870c1 which fixed the issue. Please, let me know, if you still see it after that commit!

Sorry for posting to this slightly aged thread. I'm seeing a similar error of this on 32 bit AIX PPC, where getUIntPtrType() returns unsigned long, so the aforementioned follow-on patch no longer applies. The results from getIntTypeForBitwidth() seem unreliable in certain cases (e.g. int vs long in ILP32), and I couldn't think of a good way around it. Have you had any future plans on mitigating such problems?

Hi there, what is the exact target triple?
I wonder if it would be possible to create a new unit test case where we pass somehow the target triple to runCheckerOnCode?

Hi, the target triple is powerpc-ibm-aix. Thanks.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h

CompoundValData(QualType t, llvm::ImmutableList<SVal> l) : T(t), L(l) {
     assert(NonLoc::isCompoundType(t));
   }
 
   using iterator = llvm::ImmutableList<SVal>::iterator;
 
   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<SVal> L);
 
   void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, T, L); }
 };
 
 class LazyCompoundValData : public llvm::FoldingSetNode {
   StoreRef store;

clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h

if (SE)
       return SE->symbol_begin();
     else
       return SymExpr::symbol_iterator();
   }
 
   SymExpr::symbol_iterator symbol_end() const {
     return SymExpr::symbol_end();
   }
+
+  /// Try to get a reasonable type for the given value.
+  llvm::Optional<QualType> getType() const;
 };
 
 inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) {
   V.dumpToStream(os);
   return os;
 }
 
 class UndefinedVal : public SVal {
 public:
   UndefinedVal() : SVal(UndefinedValKind) {}
 
 private:
   friend class SVal;
 
   static bool isKind(const SVal& V) {

clang/lib/StaticAnalyzer/Core/SVals.cpp

 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/Type.h"
 #include "clang/Basic/JsonSupport.h"
 #include "clang/Basic/LLVM.h"
 #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"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>())
     return X->getRegion();
 
   if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>())
     return X->getLoc().getAsRegion();
 
   return nullptr;
 }
 
+namespace {
+class TypeRetrievingVisitor
+    : public FullSValVisitor<TypeRetrievingVisitor, Optional<QualType>> {
+public:
+  Optional<QualType> VisitLocMemRegionVal(loc::MemRegionVal MRV) {
+    return Visit(MRV.getRegion());
+  }
+  Optional<QualType> VisitLocGotoLabel(loc::GotoLabel GL) {
+    return QualType{GL.getLabel()->getASTContext().VoidPtrTy};
+  }
+  Optional<QualType> VisitNonLocCompoundVal(nonloc::CompoundVal CV) {
+    return CV.getValue()->getType();
+  }
+  Optional<QualType> VisitNonLocLazyCompoundVal(nonloc::LazyCompoundVal LCV) {
+    return Visit(LCV.getRegion());
+  }
+  Optional<QualType> VisitNonLocSymbolVal(nonloc::SymbolVal SV) {
+    return Visit(SV.getSymbol());
+  }
+  Optional<QualType> VisitSymbolicRegion(const SymbolicRegion *SR) {
+    return Visit(SR->getSymbol());
+  }
+  Optional<QualType> VisitTypedRegion(const TypedRegion *TR) {
+    return TR->getLocationType();
+  }
+  Optional<QualType> VisitSymExpr(const SymExpr *SE) { return SE->getType(); }
+};
+} // end anonymous namespace
+
+Optional<QualType> SVal::getType() const {
+  TypeRetrievingVisitor TRV;
+  return TRV.Visit(*this);
+}
+
 const MemRegion *loc::MemRegionVal::stripCasts(bool StripBaseCasts) const {
   const MemRegion *R = getRegion();
   return R ?  R->StripCasts(StripBaseCasts) : nullptr;
 }
 
 const void *nonloc::LazyCompoundVal::getStore() const {
   return static_cast<const LazyCompoundValData*>(Data)->getStore();
 }

clang/unittests/StaticAnalyzer/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(StaticAnalysisTests
   AnalyzerOptionsTest.cpp
   CallDescriptionTest.cpp
   CallEventTest.cpp
   FalsePositiveRefutationBRVisitorTest.cpp
   ParamRegionTest.cpp
   RangeSetTest.cpp
   RegisterCustomCheckersTest.cpp
-  StoreTest.cpp 
+  StoreTest.cpp
   SymbolReaperTest.cpp
+  SValTest.cpp
   TestReturnValueUnderConstruction.cpp
   )
 
 clang_target_link_libraries(StaticAnalysisTests
   PRIVATE
   clangBasic
   clangAnalysis
   clangAST
   clangASTMatchers
   clangCrossTU
   clangFrontend
   clangSerialization
   clangStaticAnalyzerCore
   clangStaticAnalyzerFrontend
   clangTooling
   )

clang/unittests/StaticAnalyzer/SValTest.cpp

+//===- 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/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();
+}
+
+namespace ento {
+namespace {
+
+//===----------------------------------------------------------------------===//
+//                       Testing framework implementation
+//===----------------------------------------------------------------------===//
+
+/// A simple map from variable names to symbolic values used to init them.
+using SVals = llvm::StringMap<SVal>;
+
+/// 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<check::Bind, check::EndAnalysis> {
+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<DeclStmt>(S))
+      return;
+
+    if (const auto *VR = llvm::dyn_cast_or_null<VarRegion>(Loc.getAsRegion())) {
+      CollectedSVals[VR->getDescriptiveName(false)] = Val;
+    }
+  }
+
+  void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,
+                        ExprEngine &Engine) const {
+    if (!Tested) {
+      test(Engine);
+      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 = 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 = <expr>;
+//
+// `x` will be bound to whatever symbolic value the engine produced for <expr>.
+// 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 override;                              \
+  };                                                                           \
+                                                                               \
+  void add##NAME##SValCollector(AnalysisASTConsumer &AnalysisConsumer,         \
+                                AnalyzerOptions &AnOpts) {                     \
+    AnOpts.CheckersAndPackages = {{"test.##NAME##SValCollector", true}};       \
+    AnalysisConsumer.AddCheckerRegistrationFn([](CheckerRegistry &Registry) {  \
+      Registry.addChecker<NAME##SValCollector>("test.##NAME##SValCollector",   \
+                                               "Description", "");             \
+    });                                                                        \
+  }                                                                            \
+                                                                               \
+  TEST(SValTest, NAME) { runCheckerOnCode<add##NAME##SValCollector>(CODE); }   \
+  void NAME##SValCollector::test(ExprEngine &Engine) const
+
+//===----------------------------------------------------------------------===//
+//                                 Actual tests
+//===----------------------------------------------------------------------===//
+
+SVAL_TEST(GetTypeConst, R"(
+void foo() {
+  int x = 42;
+})") {
+  SVal X = getByName("x");
+  // TODO: Find a way how to get type of nonloc::ConcreteInt
+  EXPECT_FALSE(X.getType().hasValue());
+}
+
+SVAL_TEST(GetSymExprType, R"(
+void foo(int a, int b) {
+  int x = a;
+  int y = a + b;
+})") {
+  QualType Int = Engine.getContext().IntTy;
+
+  SVal X = getByName("x");
+  ASSERT_TRUE(X.getType().hasValue());
+  EXPECT_EQ(Int, *X.getType());
+
+  SVal Y = getByName("y");
+  ASSERT_TRUE(Y.getType().hasValue());
+  EXPECT_EQ(Int, *Y.getType());
+}
+
+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 = Engine.getContext().IntTy;
+
+  SVal A = getByName("a");
+  ASSERT_TRUE(A.getType().hasValue());
+  const auto *APtrTy = dyn_cast<PointerType>(*A.getType());
+  ASSERT_NE(APtrTy, nullptr);
+  EXPECT_EQ(Int, APtrTy->getPointeeType());
+
+  SVal B = getByName("b");
+  ASSERT_TRUE(B.getType().hasValue());
+  const auto *BPtrTy = dyn_cast<PointerType>(*B.getType());
+  ASSERT_NE(BPtrTy, nullptr);
+  EXPECT_EQ(Int, BPtrTy->getPointeeType());
+
+  SVal C = getByName("c");
+  ASSERT_TRUE(C.getType().hasValue());
+  const auto *CPtrTy = dyn_cast<PointerType>(*C.getType());
+  ASSERT_NE(CPtrTy, nullptr);
+  EXPECT_EQ(Int, CPtrTy->getPointeeType());
+
+  SVal D = getByName("d");
+  ASSERT_TRUE(D.getType().hasValue());
+  const auto *DRefTy = dyn_cast<LValueReferenceType>(*D.getType());
+  ASSERT_NE(DRefTy, nullptr);
+  EXPECT_EQ(Int, DRefTy->getPointeeType());
+
+  SVal E = getByName("e");
+  ASSERT_TRUE(E.getType().hasValue());
+  const auto *EPtrTy = dyn_cast<PointerType>(*E.getType());
+  ASSERT_NE(EPtrTy, nullptr);
+  EXPECT_EQ(Int, EPtrTy->getPointeeType());
+
+  SVal F = getByName("f");
+  ASSERT_TRUE(F.getType().hasValue());
+  const auto *FPtrTy = dyn_cast<PointerType>(*F.getType());
+  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_TRUE(A.getType().hasValue());
+  const auto *AArrayType = dyn_cast<ArrayType>(*A.getType());
+  ASSERT_NE(AArrayType, nullptr);
+  EXPECT_EQ(Engine.getContext().IntTy, AArrayType->getElementType());
+
+  SVal B = getByName("b");
+  ASSERT_TRUE(B.getType().hasValue());
+  const auto *BRecordType = dyn_cast<RecordType>(*B.getType());
+  ASSERT_NE(BRecordType, nullptr);
+  EXPECT_EQ("TestStruct", BRecordType->getDecl()->getName());
+
+  SVal C = getByName("c");
+  ASSERT_TRUE(C.getType().hasValue());
+  const auto *CRecordType = dyn_cast<RecordType>(*C.getType());
+  ASSERT_NE(CRecordType, nullptr);
+  EXPECT_EQ("TestUnion", CRecordType->getDecl()->getName());
+
+  SVal D = getByName("d");
+  ASSERT_TRUE(D.getType().hasValue());
+  const auto *DRecordType = dyn_cast<RecordType>(*D.getType());
+  ASSERT_NE(DRecordType, nullptr);
+  EXPECT_EQ("TestUnion", DRecordType->getDecl()->getName());
+}
+
+SVAL_TEST(GetStringType, R"(
+void foo() {
+  const char *a = "Hello, world!";
+}
+)") {
+  SVal A = getByName("a");
+  ASSERT_TRUE(A.getType().hasValue());
+  const auto *APtrTy = dyn_cast<PointerType>(*A.getType());
+  ASSERT_NE(APtrTy, nullptr);
+  EXPECT_EQ(Engine.getContext().CharTy, APtrTy->getPointeeType());
+}
+
+SVAL_TEST(GetThisType, R"(
+class TestClass {
+  void foo();
+};
+void TestClass::foo() {
+  const auto *a = this;
+}
+)") {
+  SVal A = getByName("a");
+  ASSERT_TRUE(A.getType().hasValue());
+  const auto *APtrTy = dyn_cast<PointerType>(*A.getType());
+  ASSERT_NE(APtrTy, nullptr);
+  const auto *ARecordType = dyn_cast<RecordType>(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_TRUE(A.getType().hasValue());
+  const auto *APtrTy = dyn_cast<PointerType>(*A.getType());
+  ASSERT_NE(APtrTy, nullptr);
+  ASSERT_TRUE(isa<FunctionProtoType>(APtrTy->getPointeeType()));
+}
+
+SVAL_TEST(GetLabelType, R"(
+void foo() {
+  entry:
+  void *a = &&entry;
+  char *b = (char *)&&entry;
+}
+)") {
+  SVal A = getByName("a");
+  ASSERT_TRUE(A.getType().hasValue());
+  EXPECT_EQ(Engine.getContext().VoidPtrTy, *A.getType());
+
+  SVal B = getByName("a");
+  ASSERT_TRUE(B.getType().hasValue());
+  EXPECT_EQ(Engine.getContext().VoidPtrTy, *B.getType());
+}
+
+} // namespace
+} // namespace ento
+} // namespace clang