[Analyzer] Support for the new variadic isa<> and isa_and_not_null<> in CastValueChecker

[baloghadamsoftware]

Summary

llvm::isa<>() and llvm::isa_and_not_null<>() template functions recently became variadic. Unfortunately this causes crashes in case of isa_and_not_null<>() and incorrect behavior in isa<>(). This patch fixes this issue (47037).

[baloghadamsoftware]

This patch intends to fix bug 47037. It is still work in progress with lots of debug printouts.

I described the issue with this patch at the bug report:

The variadic tests fail because the whole Dyanamic Type library is extremely poor design: it stores the pointers and references as they are instead of the underlying types. Unfortunately, cast<> functions which can take pointers have pointers to SubstTemplateTypeParmType but isa<> functions take everything by reference. Thus they have a reference to a SubstTemplateTypeParmType which contains the pointer. The two will never match even if I unpack the reference for the isa<> functions and get to the pointer itself because I cannot create a new pointer type in the cast<> functions where SubstTemplateTypeParmType is inside the pointer. I did not found any method to remove SubstTemplateTypeParmType from a pointer either.

This results that the test evalNonNullParamNonNullReturnReference() passes only by chance in the original version. Even if I fix the parameter which should have been pointer instead of reference the early exit blocks which use dyn_cast<> store a different "from" type for the casts that we retrieve later at the isa<> calls. This way both true and false branches for the isa<> blocks remain alive. If I extend the tests for variadic templates we are not lucky anymore, the tests fail.

[baloghadamsoftware]

My proposal is the following: do not store the casing info between pointers and references but the underlying types themselves. There are two ways to implement this: in the checkers using it (currently only this one) or behind the API of DynamicCastInfo. Maybe the latter is more appropriate.

To be fully correct we should not only change the DynamicCastInfo but also the DynamicTypeInfo: if the dynamic type of an object behind a pointer is known, then it remains the same also if we get a reference from the pointer or substitute a type for a template type parameter with it. (We can create new pointer or reference type using ASTContext.)

[baloghadamsoftware]

Working version. Debug printouts removed.

[NoQ]

Thanks!!

Could you also unforget the diff context? >.<

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

270–272

We shouldn't crash when code under analysis doesn't match our expectation.

315

Let's return immediately after the transition instead. Like, generally, it's a good practice to return immediately after a transition if you don't plan any more state splits, because otherwise it's too easy to accidentally introduce unwanted state splits.

482

Looks like a leftover debug print.

[gamesh411]

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

265

Do we intentionally skip the last arg with this loop boundary, or is the loop variable just off-by-one?

[baloghadamsoftware]

Updated according to the comments.

[baloghadamsoftware]

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

270–272

The question is whether we can get any other template argument kind for llvm::isa<>() and llvm::isa_and_nonnull<>() than Type or Pack?

315

Now I inserted a return but only if this is a known conversion. If this is an assumption, the we should assume every type in the template argument list.

[martong]

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

270–272

I think it is worth to ponder about the below case. What if isa is used in a dependent context (i.e. it is used inside another template)?

/// The template argument is an expression, and we've not resolved it to one
/// of the other forms yet, either because it's dependent or because we're
/// representing a non-canonical template argument (for instance, in a
/// TemplateSpecializationType).
Expression,

[NoQ]

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

270–272

Aha, yup, that's better, thanks.

The question is whether we can get any other template argument kind for llvm::isa<>() and llvm::isa_and_nonnull<>() than Type or Pack?

It's a more general problem: what about a completely unrelated template function that is accidentally called llvm::isa<>() or llvm::isa_and_nonnull<>()? Or what if llvm::isa<>()'s/ llvm::isa_and_nonnull<>()'s implementation changes again? If it's at all possible in any template function, we should take it into account and at least provide an early return, we shouldn't rule out that possibility by looking at the name only.

I think it is worth to ponder about the below case. What if isa is used in a dependent context (i.e. it is used inside another template)?

Ok, this one probably doesn't happen, because we don't ever try to symbolically execute templated ASTs (that aren't fully instantiated).

289

Hmm, is this phabricator's way of displaying tabs?

[whisperity]

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

289

I believe it is not displaying tabs, but rather just indicating that the current line changed in a way that only the indentation has changed... instead of marking the old side of the diff red. The HTML element is span.depth-in. A span.depth-out is red, and the arrow points the other way.

But I agree this is a new thing since the version update.

[baloghadamsoftware]

@NoQ Thank you for the review. Please also review D85752 after my update and tell me what I have to change there if it is not acceptable yet. This patch depends on that one.

[NoQ]

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

289

Aha, ok, nice!

[NoQ]

Hans is pinging us on Bugzilla because this patch is marked as a release blocker (and i believe that it indeed is). I think we should land these patches.

[steakhal]

In D85728#2237006, @NoQ wrote:

Hans is pinging us on Bugzilla because this patch is marked as a release blocker (and i believe that it indeed is). I think we should land these patches.

I believe @baloghadamsoftware is on vacation.
I'm sure he won't be mad if you commit on his behalf.

[baloghadamsoftware]

I was indeed on vacation, so thanks for committing it, @NoQ! I was waiting for agreement for the prerequisite patch then I forgot to notify you that I was going on vacation.

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

return C.getNoteTag(
         Out << ' ' << (CastSucceeds ? "is a" : "is not a") << " '" << CastToName
             << '\'';
 
         return std::string(Out.str());
       },
       /*IsPrunable=*/true);
 }
 
+static const NoteTag *getNoteTag(CheckerContext &C,
+                                 SmallVector<QualType, 4> CastToTyVec,
+                                 const Expr *Object,
+                                 bool IsKnownCast) {
+  Object = Object->IgnoreParenImpCasts();
+
+  return C.getNoteTag(
+      [=]() -> std::string {
+        SmallString<128> Msg;
+        llvm::raw_svector_ostream Out(Msg);
+
+        if (!IsKnownCast)
+          Out << "Assuming ";
+
+        if (const auto *DRE = dyn_cast<DeclRefExpr>(Object)) {
+          Out << '\'' << DRE->getDecl()->getNameAsString() << '\'';
+        } else if (const auto *ME = dyn_cast<MemberExpr>(Object)) {
+          Out << (IsKnownCast ? "Field '" : "field '")
+              << ME->getMemberDecl()->getNameAsString() << '\'';
+        } else {
+          Out << (IsKnownCast ? "The object" : "the object");
+        }
+        Out << " is";
+
+        bool First = true;
+        for (QualType CastToTy: CastToTyVec) {
+          std::string CastToName =
+            CastToTy->getAsCXXRecordDecl() ?
+            CastToTy->getAsCXXRecordDecl()->getNameAsString() :
+            CastToTy->getPointeeCXXRecordDecl()->getNameAsString();
+          Out << ' ' << ((CastToTyVec.size() == 1) ? "not" :
+                         (First ? "neither" : "nor")) << " a '" << CastToName
+              << '\'';
+          First = false;
+        }
+
+        return std::string(Out.str());
+      },
+      /*IsPrunable=*/true);
+}
+
 //===----------------------------------------------------------------------===//
 // Main logic to evaluate a cast.
 //===----------------------------------------------------------------------===//
 
 static QualType alignReferenceTypes(QualType toAlign, QualType alignTowards,
                                     ASTContext &ACtx) {
   if (alignTowards->isLValueReferenceType() &&
       alignTowards.isConstQualified()) {

 }
 
 static void addInstanceOfTransition(const CallEvent &Call,
                                     DefinedOrUnknownSVal DV,
                                     ProgramStateRef State, CheckerContext &C,
                                     bool IsInstanceOf) {
   const FunctionDecl *FD = Call.getDecl()->getAsFunction();
   QualType CastFromTy = Call.parameters()[0]->getType();
-  QualType CastToTy = FD->getTemplateSpecializationArgs()->get(0).getAsType();
+  SmallVector<QualType, 4> CastToTyVec;
+  for (unsigned idx = 0; idx < FD->getTemplateSpecializationArgs()->size() - 1;
+       ++idx) {
+    TemplateArgument CastToTempArg =
+      FD->getTemplateSpecializationArgs()->get(idx);
+    switch (CastToTempArg.getKind()) {
+    default:
+      return;
+    case TemplateArgument::Type:
+      CastToTyVec.push_back(CastToTempArg.getAsType());
+      break;
+    case TemplateArgument::Pack:
+      for (TemplateArgument ArgInPack: CastToTempArg.pack_elements())
+        CastToTyVec.push_back(ArgInPack.getAsType());
+      break;
+    }
+  }
+
+  const MemRegion *MR = DV.getAsRegion();
+  if (MR && CastFromTy->isReferenceType())
+    MR = State->getSVal(DV.castAs<Loc>()).getAsRegion();
+
+  bool Success = false;
+  bool IsAnyKnown = false;
+  for (QualType CastToTy: CastToTyVec) {
     if (CastFromTy->isPointerType())
       CastToTy = C.getASTContext().getPointerType(CastToTy);
     else if (CastFromTy->isReferenceType())
       CastToTy = alignReferenceTypes(CastToTy, CastFromTy, C.getASTContext());
     else
       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;
-  }
-
     // Store the type and the cast information.
     bool IsKnownCast = CastInfo || CastFromTy == CastToTy;
+    IsAnyKnown = IsAnyKnown || IsKnownCast;
+    ProgramStateRef NewState = State;
     if (!IsKnownCast)
-    State = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,
+      NewState = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,
                                            IsInstanceOf);
 
+    if (CastSucceeds) {
+      Success = true;
       C.addTransition(
-      State->BindExpr(Call.getOriginExpr(), C.getLocationContext(),
-                      C.getSValBuilder().makeTruthVal(CastSucceeds)),
-      getNoteTag(C, CastInfo, CastToTy, Call.getArgExpr(0), CastSucceeds,
+          NewState->BindExpr(Call.getOriginExpr(), C.getLocationContext(),
+                             C.getSValBuilder().makeTruthVal(true)),
+          getNoteTag(C, CastInfo, CastToTy, Call.getArgExpr(0), true,
                      IsKnownCast));
+      if (IsKnownCast)
+        return;
+    } else if (CastInfo && CastInfo->succeeds()) {
+      C.generateSink(NewState, C.getPredecessor());
+      return;
+    }
+  }
+
+  if (!Success) {
+    C.addTransition(
+        State->BindExpr(Call.getOriginExpr(), C.getLocationContext(),
+                        C.getSValBuilder().makeTruthVal(false)),
+        getNoteTag(C, CastToTyVec, Call.getArgExpr(0), IsAnyKnown));
+  }
 }
 
 //===----------------------------------------------------------------------===//
 // Evaluating cast, dyn_cast, cast_or_null, dyn_cast_or_null.
 //===----------------------------------------------------------------------===//
 
 static void evalNonNullParamNonNullReturn(const CallEvent &Call,
                                           DefinedOrUnknownSVal DV,
bool CastValueChecker::evalCall(const CallEvent &Call,
   switch (Kind) {
   case CallKind::Function: {
     // 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()))
+        !(ParamT->isReferenceType() && ResultT->isReferenceType())) {
       return false;
+    }
 
     DV = Call.getArgSVal(0).getAs<DefinedOrUnknownSVal>();
     break;
   }
   case CallKind::InstanceOf: {
     // We need to obtain the only template argument to determinte the type.
     const FunctionDecl *FD = Call.getDecl()->getAsFunction();
     if (!FD || !FD->getTemplateSpecializationArgs())

clang/test/Analysis/Inputs/llvm.h

 template <class X, class Y>
 const X *cast_or_null(Y Value);
 
 template <class X, class Y>
 const X *dyn_cast_or_null(Y *Value);
 template <class X, class Y>
 const X *dyn_cast_or_null(Y &Value);
 
-template <class X, class Y>
-bool isa(Y Value);
+template <class X, class Y> inline bool isa(const Y &Val);
 
-template <class X, class Y>
-bool isa_and_nonnull(Y Value);
+template <typename First, typename Second, typename... Rest, typename Y>
+inline bool isa(const Y &Val) {
+  return isa<First>(Val) || isa<Second, Rest...>(Val);
+}
+
+template <typename... X, class Y>
+inline bool isa_and_nonnull(const Y &Val) {
+  if (!Val)
+    return false;
+  return isa<X...>(Val);
+}
 
 template <typename X, typename Y>
 std::unique_ptr<X> cast(std::unique_ptr<Y> &&Value);
 } // namespace llvm

clang/test/Analysis/cast-value-logic.cpp

struct Shape {
   const T *castAs() const;
 
   template <typename T>
   const T *getAs() const;
 
   virtual double area();
 };
 class Triangle : public Shape {};
+class Rectangle : public Shape {};
+class Hexagon : public Shape {};
 class Circle : public Shape {
 public:
   ~Circle();
 };
 class SuspiciouslySpecificCircle : public Circle {};
 } // namespace clang
 
 using namespace llvm;
 using namespace clang;
 
 void test_regions_dyn_cast(const Shape *A, const Shape *B) {
   if (dyn_cast<Circle>(A) && !dyn_cast<Circle>(B))
     clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
 }
 
 void test_regions_isa(const Shape *A, const Shape *B) {
   if (isa<Circle>(A) && !isa<Circle>(B))
     clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
 }
 
+void test_regions_isa_variadic(const Shape *A, const Shape *B) {
+  if (isa<Triangle, Rectangle, Hexagon>(A) &&
+      !isa<Rectangle, Hexagon, Circle>(B))
+    clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+}
+
+void test_regions_isa_and_nonnull(const Shape *A, const Shape *B) {
+  if (isa_and_nonnull<Circle>(A) && !isa_and_nonnull<Circle>(B))
+    clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+}
+
+void test_regions_isa_and_nonnull_variadic(const Shape *A, const Shape *B) {
+  if (isa_and_nonnull<Triangle, Rectangle, Hexagon>(A) &&
+      !isa_and_nonnull<Rectangle, Hexagon, Circle>(B))
+    clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+}
+
 namespace test_cast {
 void evalLogic(const Shape *S) {
   const Circle *C = cast<Circle>(S);
   clang_analyzer_numTimesReached(); // expected-warning {{1}}
 
   if (S && C)
     clang_analyzer_eval(C == S); // expected-warning {{TRUE}}
 

clang/test/Analysis/cast-value-notes.cpp

 // RUN: %clang_analyze_cc1 -std=c++14 \
 // RUN:  -analyzer-checker=core,apiModeling.llvm.CastValue,debug.ExprInspection\
 // RUN:  -analyzer-output=text -verify %s
 
 #include "Inputs/llvm.h"
 
 namespace clang {
 struct Shape {
   template <typename T>
   const T *castAs() const;
 
   template <typename T>
   const T *getAs() const;
 };
 class Triangle : public Shape {};
+class Rectangle : public Shape {};
+class Hexagon : public Shape {};
 class Circle : public Shape {};
 } // namespace clang
 
 using namespace llvm;
 using namespace clang;
 
 void evalReferences(const Shape &S) {
   const auto &C = dyn_cast<Circle>(S);
   // expected-note@-1 {{Assuming 'S' is not a 'Circle'}}
   // expected-note@-2 {{Dereference of null pointer}}
   // expected-warning@-3 {{Dereference of null pointer}}
 }
 
 void evalNonNullParamNonNullReturnReference(const Shape &S) {
-  // Unmodeled cast from reference to pointer.
   const auto *C = dyn_cast_or_null<Circle>(S);
   // expected-note@-1 {{'C' initialized here}}
 
   if (!dyn_cast_or_null<Circle>(C)) {
     // expected-note@-1 {{'C' is a 'Circle'}}
     // expected-note@-2 {{Taking false branch}}
     return;
   }
 
   if (dyn_cast_or_null<Triangle>(C)) {
     // expected-note@-1 {{Assuming 'C' is not a 'Triangle'}}
     // expected-note@-2 {{Taking false branch}}
     return;
   }
 
+  if (dyn_cast_or_null<Rectangle>(C)) {
+    // expected-note@-1 {{Assuming 'C' is not a 'Rectangle'}}
+    // expected-note@-2 {{Taking false branch}}
+    return;
+  }
+
+  if (dyn_cast_or_null<Hexagon>(C)) {
+    // expected-note@-1 {{Assuming 'C' is not a 'Hexagon'}}
+    // expected-note@-2 {{Taking false branch}}
+    return;
+  }
+
   if (isa<Triangle>(C)) {
     // expected-note@-1 {{'C' is not a 'Triangle'}}
     // expected-note@-2 {{Taking false branch}}
     return;
   }
 
-  if (isa<Circle>(C)) {
+  if (isa<Triangle, Rectangle>(C)) {
+    // expected-note@-1 {{'C' is neither a 'Triangle' nor a 'Rectangle'}}
+    // expected-note@-2 {{Taking false branch}}
+    return;
+  }
+
+  if (isa<Triangle, Rectangle, Hexagon>(C)) {
+    // expected-note@-1 {{'C' is neither a 'Triangle' nor a 'Rectangle' nor a 'Hexagon'}}
+    // expected-note@-2 {{Taking false branch}}
+    return;
+  }
+
+  if (isa<Circle, Rectangle, Hexagon>(C)) {
     // expected-note@-1 {{'C' is a 'Circle'}}
     // expected-note@-2 {{Taking true branch}}
 
     (void)(1 / !C);
     // expected-note@-1 {{'C' is non-null}}
     // expected-note@-2 {{Division by zero}}
     // expected-warning@-3 {{Division by zero}}
   }
 }
 
 void evalNonNullParamNonNullReturn(const Shape *S) {
   const auto *C = cast<Circle>(S);
   // expected-note@-1 {{'S' is a 'Circle'}}
   // expected-note@-2 {{'C' initialized here}}
 
-  if (!isa<Triangle>(C)) {
-    // expected-note@-1 {{Assuming 'C' is a 'Triangle'}}
+  if (!dyn_cast_or_null<Circle>(C)) {
+    // expected-note@-1 {{'C' is a 'Circle'}}
+    // expected-note@-2 {{Taking false branch}}
+    return;
+  }
+
+  if (dyn_cast_or_null<Triangle>(C)) {
+    // expected-note@-1 {{Assuming 'C' is not a 'Triangle'}}
+    // expected-note@-2 {{Taking false branch}}
+    return;
+  }
+
+  if (dyn_cast_or_null<Rectangle>(C)) {
+    // expected-note@-1 {{Assuming 'C' is not a 'Rectangle'}}
+    // expected-note@-2 {{Taking false branch}}
+    return;
+  }
+
+  if (dyn_cast_or_null<Hexagon>(C)) {
+    // expected-note@-1 {{Assuming 'C' is not a 'Hexagon'}}
     // expected-note@-2 {{Taking false branch}}
     return;
   }
 
-  if (!isa<Triangle>(C)) {
-    // expected-note@-1 {{'C' is a 'Triangle'}}
+  if (isa<Triangle>(C)) {
+    // expected-note@-1 {{'C' is not a 'Triangle'}}
     // expected-note@-2 {{Taking false branch}}
     return;
   }
 
+  if (isa<Triangle, Rectangle>(C)) {
+    // expected-note@-1 {{'C' is neither a 'Triangle' nor a 'Rectangle'}}
+    // expected-note@-2 {{Taking false branch}}
+    return;
+  }
+
+  if (isa<Triangle, Rectangle, Hexagon>(C)) {
+    // expected-note@-1 {{'C' is neither a 'Triangle' nor a 'Rectangle' nor a 'Hexagon'}}
+    // expected-note@-2 {{Taking false branch}}
+    return;
+  }
+
+  if (isa<Circle, Rectangle, Hexagon>(C)) {
+    // expected-note@-1 {{'C' is a 'Circle'}}
+    // expected-note@-2 {{Taking true branch}}
+
     (void)(1 / !C);
     // expected-note@-1 {{'C' is non-null}}
     // expected-note@-2 {{Division by zero}}
     // expected-warning@-3 {{Division by zero}}
   }
+}
 
 void evalNonNullParamNullReturn(const Shape *S) {
   const auto *C = dyn_cast_or_null<Circle>(S);
   // expected-note@-1 {{Assuming 'S' is not a 'Circle'}}
 
   if (const auto *T = dyn_cast_or_null<Triangle>(S)) {
     // expected-note@-1 {{Assuming 'S' is a 'Triangle'}}
     // expected-note@-2 {{'T' initialized here}}