[analyzer] Support modelling no-op BaseToDerived casts in ExprEngine

[NoQ]

Tried to address the regression with double inheritance by introducing a CXXDerivedObjectRegion, which is the opposite of CXXBaseObjectRegion, to represent such casts. Such region is a bit weird because it is by design bigger than its super-region. But it's not harmful when it is put on top of a SymbolicRegion that has unknown extent anyway.

Offset computation for CXXDerivedObjectRegion and proper modeling of casts still remains to be implemented. It seems to be useful to keep the base class decl as part of the region's identity, but i didn't do that yet.

In any case, it addresses the regression that i was thinking of: otherwise, in the base_to_derived_double_inheritance test it'd think that x, rather than y, was set.

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

public:
   const MemSpaceRegion *getMemorySpace() const;
 
   const MemRegion *getBaseRegion() const;
 
   /// Check if the region is a subregion of the given region.
   /// Each region is a subregion of itself.
   virtual bool isSubRegionOf(const MemRegion *R) const;
 
-  const MemRegion *StripCasts(bool StripBaseCasts = true) const;
+  const MemRegion *StripCasts(bool StripBaseAndDerivedCasts = true) const;
 
   /// If this is a symbolic region, returns the region. Otherwise,
   /// goes up the base chain looking for the first symbolic base region.
   const SymbolicRegion *getSymbolicBase() const;
 
   bool hasGlobalsOrParametersStorage() const;
 
   bool hasStackStorage() const;
public:
 
   void printPrettyAsExpr(raw_ostream &os) const override;
 
   static bool classof(const MemRegion *region) {
     return region->getKind() == CXXBaseObjectRegionKind;
   }
 };
 
+// CXXDerivedObjectRegion represents a derived-class object that surrounds
+// a C++ object. It is identified by the derived class declaration and the
+// region of its parent object. It is a bit counter-intuitive (but not otherwise
+// unseen) that this region represents a larger segment of memory that its
+// super-region.
+class CXXDerivedObjectRegion : public TypedValueRegion {
+  friend class MemRegionManager;
+
+  const CXXRecordDecl *DerivedD;
+
+  CXXDerivedObjectRegion(const CXXRecordDecl *DerivedD, const SubRegion *SReg)
+      : TypedValueRegion(SReg, CXXDerivedObjectRegionKind), DerivedD(DerivedD) {
+    assert(DerivedD);
+    // In case of a concrete region, it should always be possible to model
+    // the base-to-derived cast by undoing a previous derived-to-base cast,
+    // otherwise the cast is most likely ill-formed.
+    assert(SReg->getSymbolicBase() &&
+           "Should have unwrapped a base region instead!");
+  }
+
+  static void ProfileRegion(llvm::FoldingSetNodeID &ID, const CXXRecordDecl *RD,
+                            const MemRegion *SReg);
+
+public:
+  const CXXRecordDecl *getDecl() const { return DerivedD; }
+
+  QualType getValueType() const override;
+
+  void dumpToStream(raw_ostream &os) const override;
+
+  void Profile(llvm::FoldingSetNodeID &ID) const override;
+
+  bool canPrintPrettyAsExpr() const override;
+
+  void printPrettyAsExpr(raw_ostream &os) const override;
+
+  static bool classof(const MemRegion *region) {
+    return region->getKind() == CXXDerivedObjectRegionKind;
+  }
+};
+
 template<typename RegionTy>
 const RegionTy* MemRegion::getAs() const {
   if (const auto *RT = dyn_cast<RegionTy>(this))
     return RT;
 
   return nullptr;
 }
 
public:
   /// super region.
   const CXXBaseObjectRegion *
   getCXXBaseObjectRegionWithSuper(const CXXBaseObjectRegion *baseReg,
                                   const SubRegion *superRegion) {
     return getCXXBaseObjectRegion(baseReg->getDecl(), superRegion,
                                   baseReg->isVirtual());
   }
 
+  /// Create a CXXDerivedObjectRegion with the given derived class for region
+  /// \p Super. This should not be used for casting an existing
+  /// CXXBaseObjectRegion back to the derived type; instead, CXXBaseObjectRegion
+  /// should be removed.
+  const CXXDerivedObjectRegion *
+  getCXXDerivedObjectRegion(const CXXRecordDecl *BaseClass,
+                            const SubRegion *Super);
+
   const FunctionCodeRegion *getFunctionCodeRegion(const NamedDecl *FD);
   const BlockCodeRegion *getBlockCodeRegion(const BlockDecl *BD,
                                             CanQualType locTy,
                                             AnalysisDeclContext *AC);
 
   /// getBlockDataRegion - Get the memory region associated with an instance
   ///  of a block.  Unlike many other MemRegions, the LocationContext*
   ///  argument is allowed to be NULL for cases where we have no known

include/clang/StaticAnalyzer/Core/PathSensitive/Regions.def

ABSTRACT_REGION(TypedRegion, SubRegion)
     ABSTRACT_REGION(CodeTextRegion, TypedRegion)
       REGION(BlockCodeRegion, CodeTextRegion)
       REGION(FunctionCodeRegion, CodeTextRegion)
       REGION_RANGE(CODE_TEXT_REGIONS, BlockCodeRegionKind,
                                       FunctionCodeRegionKind)
     ABSTRACT_REGION(TypedValueRegion, TypedRegion)
       REGION(CompoundLiteralRegion, TypedValueRegion)
       REGION(CXXBaseObjectRegion, TypedValueRegion)
+      REGION(CXXDerivedObjectRegion, TypedValueRegion)
       REGION(CXXTempObjectRegion, TypedValueRegion)
       REGION(CXXThisRegion, TypedValueRegion)
       ABSTRACT_REGION(DeclRegion, TypedValueRegion)
         REGION(FieldRegion, DeclRegion)
         REGION(ObjCIvarRegion, DeclRegion)
         REGION(VarRegion, DeclRegion)
         REGION_RANGE(DECL_REGIONS, FieldRegionKind,
                                    VarRegionKind)

lib/StaticAnalyzer/Core/MemRegion.cpp

 QualType ObjCIvarRegion::getValueType() const {
   return getDecl()->getType();
 }
 
 QualType CXXBaseObjectRegion::getValueType() const {
   return QualType(getDecl()->getTypeForDecl(), 0);
 }
 
+QualType CXXDerivedObjectRegion::getValueType() const {
+  return QualType(getDecl()->getTypeForDecl(), 0);
+}
+
 //===----------------------------------------------------------------------===//
 // FoldingSet profiling.
 //===----------------------------------------------------------------------===//
 
 void MemSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
   ID.AddInteger(static_cast<unsigned>(getKind()));
 }
 
void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
   ID.AddBoolean(IsVirtual);
   ID.AddPointer(SReg);
 }
 
 void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
   ProfileRegion(ID, getDecl(), isVirtual(), superRegion);
 }
 
+void CXXDerivedObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
+                                           const CXXRecordDecl *RD,
+                                           const MemRegion *SReg) {
+  ID.AddPointer(RD);
+  ID.AddPointer(SReg);
+}
+
+void CXXDerivedObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
+  ProfileRegion(ID, getDecl(), superRegion);
+}
+
 //===----------------------------------------------------------------------===//
 // Region anchors.
 //===----------------------------------------------------------------------===//
 
 void GlobalsSpaceRegion::anchor() {}
 
 void NonStaticGlobalSpaceRegion::anchor() {}
 

 }
 
 void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
   os << "temp_object{" << getValueType().getAsString() << ','
      << static_cast<const void *>(Ex) << '}';
 }
 
 void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
-  os << "base{" << superRegion << ',' << getDecl()->getName() << '}';
+  os << "Base{" << superRegion << ',' << getDecl()->getName() << '}';
+}
+
+void CXXDerivedObjectRegion::dumpToStream(raw_ostream &os) const {
+  os << "Derived{" << superRegion << ',' << getDecl()->getName() << '}';
 }
 
 void CXXThisRegion::dumpToStream(raw_ostream &os) const {
   os << "this";
 }
 
 void ElementRegion::dumpToStream(raw_ostream &os) const {
-  os << "element{" << superRegion << ','
+  os << "Element{" << superRegion << ','
      << Index << ',' << getElementType().getAsString() << '}';
 }
 
 void FieldRegion::dumpToStream(raw_ostream &os) const {
   os << superRegion << "->" << *getDecl();
 }
 
 void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
-  os << "ivar{" << superRegion << ',' << *getDecl() << '}';
+  os << "Ivar{" << superRegion << ',' << *getDecl() << '}';
 }
 
 void StringRegion::dumpToStream(raw_ostream &os) const {
   assert(Str != nullptr && "Expecting non-null StringLiteral");
   Str->printPretty(os, nullptr, PrintingPolicy(getContext().getLangOpts()));
 }
 
 void ObjCStringRegion::dumpToStream(raw_ostream &os) const {

 bool CXXBaseObjectRegion::canPrintPrettyAsExpr() const {
   return superRegion->canPrintPrettyAsExpr();
 }
 
 void CXXBaseObjectRegion::printPrettyAsExpr(raw_ostream &os) const {
   superRegion->printPrettyAsExpr(os);
 }
 
+bool CXXDerivedObjectRegion::canPrintPrettyAsExpr() const {
+  return superRegion->canPrintPrettyAsExpr();
+}
+
+void CXXDerivedObjectRegion::printPrettyAsExpr(raw_ostream &os) const {
+  superRegion->printPrettyAsExpr(os);
+}
+
 std::string MemRegion::getDescriptiveName(bool UseQuotes) const {
   std::string VariableName;
   std::string ArrayIndices;
   const MemRegion *R = this;
   SmallString<50> buf;
   llvm::raw_svector_ostream os(buf);
 
   // Obtain array indices to add them to the variable name.
if (IsVirtual) {
         Super = cast<SubRegion>(Base->getSuperRegion());
       assert(Super && !isa<MemSpaceRegion>(Super));
     }
   }
 
   return getSubRegion<CXXBaseObjectRegion>(RD, IsVirtual, Super);
 }
 
+const CXXDerivedObjectRegion *
+MemRegionManager::getCXXDerivedObjectRegion(const CXXRecordDecl *RD,
+                                            const SubRegion *Super) {
+  return getSubRegion<CXXDerivedObjectRegion>(RD, Super);
+}
+
 const CXXThisRegion*
 MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
                                    const LocationContext *LC) {
   const auto *PT = thisPointerTy->getAs<PointerType>();
   assert(PT);
   // Inside the body of the operator() of a lambda a this expr might refer to an
   // object in one of the parent location contexts.
   const auto *D = dyn_cast<CXXMethodDecl>(LC->getDecl());

 const MemRegion *MemRegion::getBaseRegion() const {
   const MemRegion *R = this;
   while (true) {
     switch (R->getKind()) {
       case MemRegion::ElementRegionKind:
       case MemRegion::FieldRegionKind:
       case MemRegion::ObjCIvarRegionKind:
       case MemRegion::CXXBaseObjectRegionKind:
+      case MemRegion::CXXDerivedObjectRegionKind:
         R = cast<SubRegion>(R)->getSuperRegion();
         continue;
       default:
         break;
     }
     break;
   }
   return R;
 }
 
 bool MemRegion::isSubRegionOf(const MemRegion *R) const {
   return false;
 }
 
 //===----------------------------------------------------------------------===//
 // View handling.
 //===----------------------------------------------------------------------===//
 
-const MemRegion *MemRegion::StripCasts(bool StripBaseCasts) const {
+const MemRegion *MemRegion::StripCasts(bool StripBaseAndDerivedCasts) const {
   const MemRegion *R = this;
   while (true) {
     switch (R->getKind()) {
     case ElementRegionKind: {
       const auto *ER = cast<ElementRegion>(R);
       if (!ER->getIndex().isZeroConstant())
         return R;
       R = ER->getSuperRegion();
       break;
     }
     case CXXBaseObjectRegionKind:
-      if (!StripBaseCasts)
+    case CXXDerivedObjectRegionKind:
+      if (!StripBaseAndDerivedCasts)
         return R;
-      R = cast<CXXBaseObjectRegion>(R)->getSuperRegion();
+      R = cast<TypedValueRegion>(R)->getSuperRegion();
       break;
     default:
       return R;
     }
   }
 }
 
 const SymbolicRegion *MemRegion::getSymbolicBase() const {
case MemRegion::CXXBaseObjectRegionKind: {
         BaseOffset = Layout.getVBaseClassOffset(BOR->getDecl());
       else
         BaseOffset = Layout.getBaseClassOffset(BOR->getDecl());
 
       // The base offset is in chars, not in bits.
       Offset += BaseOffset.getQuantity() * R->getContext().getCharWidth();
       break;
     }
+
+    case MemRegion::CXXDerivedObjectRegionKind: {
+      // TODO: Store the base type in the CXXDerivedObjectRegion and use it.
+      goto Finish;
+    }
+
     case MemRegion::ElementRegionKind: {
       const auto *ER = cast<ElementRegion>(R);
       R = ER->getSuperRegion();
 
       QualType EleTy = ER->getValueType();
       if (EleTy->isIncompleteType()) {
         // We cannot compute the offset of the base class.
         SymbolicOffsetBase = R;

lib/StaticAnalyzer/Core/RegionStore.cpp

explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k)
     assert(getConcreteOffsetRegion() == Base && "Failed to store base region");
   }
 
   /// Create a key for a binding at \p offset from base region \p r.
   explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k)
     : P(r, k), Data(offset) {
     assert(r && "Must have known regions.");
     assert(getOffset() == offset && "Failed to store offset");
-    assert((r == r->getBaseRegion() || isa<ObjCIvarRegion>(r)) && "Not a base");
+    assert((r == r->getBaseRegion() || isa<ObjCIvarRegion>(r) ||
+            isa <CXXDerivedObjectRegion>(r)) &&
+           "Not a base");
   }
 public:
 
   bool isDirect() const { return P.getInt() & Direct; }
   bool hasSymbolicOffset() const { return P.getInt() & Symbolic; }
 
   const MemRegion *getRegion() const { return P.getPointer(); }
   uint64_t getOffset() const {

lib/StaticAnalyzer/Core/Store.cpp

switch (R->getKind()) {
     case MemRegion::AllocaRegionKind:
     case MemRegion::CompoundLiteralRegionKind:
     case MemRegion::FieldRegionKind:
     case MemRegion::ObjCIvarRegionKind:
     case MemRegion::ObjCStringRegionKind:
     case MemRegion::VarRegionKind:
     case MemRegion::CXXTempObjectRegionKind:
     case MemRegion::CXXBaseObjectRegionKind:
+    case MemRegion::CXXDerivedObjectRegionKind:
       return MakeElementRegion(cast<SubRegion>(R), PointeeTy);
 
     case MemRegion::ElementRegionKind: {
       // If we are casting from an ElementRegion to another type, the
       // algorithm is as follows:
       //
       // (1) Compute the "raw offset" of the ElementRegion from the
       //     base region.  This is done by calling 'getAsRawOffset()'.
SVal StoreManager::evalDerivedToBase(SVal Derived, const CXXBasePath &Path) {
   for (const auto &I : Path)
     Result = evalDerivedToBase(Result, I.Base->getType(),
                                I.Base->isVirtual());
   return Result;
 }
 
 SVal StoreManager::evalDerivedToBase(SVal Derived, QualType BaseType,
                                      bool IsVirtual) {
-  Optional<loc::MemRegionVal> DerivedRegVal =
-      Derived.getAs<loc::MemRegionVal>();
-  if (!DerivedRegVal)
+  const MemRegion *DerivedReg = Derived.getAsRegion();
+  if (!DerivedReg)
     return Derived;
 
   const CXXRecordDecl *BaseDecl = BaseType->getPointeeCXXRecordDecl();
   if (!BaseDecl)
     BaseDecl = BaseType->getAsCXXRecordDecl();
   assert(BaseDecl && "not a C++ object?");
 
+  if (const auto *AlreadyDerivedReg =
+          dyn_cast<CXXDerivedObjectRegion>(DerivedReg)) {
+    if (const auto *SR =
+            dyn_cast<SymbolicRegion>(AlreadyDerivedReg->getSuperRegion()))
+      if (SR->getSymbol()->getType()->getPointeeCXXRecordDecl() == BaseDecl)
+        return loc::MemRegionVal(SR);
+
+    DerivedReg = AlreadyDerivedReg->getSuperRegion();
+  }
+
   const MemRegion *BaseReg = MRMgr.getCXXBaseObjectRegion(
-      BaseDecl, cast<SubRegion>(DerivedRegVal->getRegion()), IsVirtual);
+      BaseDecl, cast<SubRegion>(DerivedReg), IsVirtual);
 
   return loc::MemRegionVal(BaseReg);
 }
 
 /// Returns the static type of the given region, if it represents a C++ class
 /// object.
 ///
 /// This handles both fully-typed regions, where the dynamic type is known, and
if (Uncasted == MR) {
       // class. We must be casting the base to derived, so the cast should
       // fail.
       break;
     }
 
     MR = Uncasted;
   }
 
+  if (const auto *SR = dyn_cast<SymbolicRegion>(MR)) {
+    return loc::MemRegionVal(MRMgr.getCXXDerivedObjectRegion(TargetClass, SR));
+  }
+
   // We failed if the region we ended up with has perfect type info.
   Failed = isa<TypedValueRegion>(MR);
   return UnknownVal();
 }
 
 /// CastRetrievedVal - Used by subclasses of StoreManager to implement
 ///  implicit casts that arise from loads from regions that are reinterpreted
 ///  as another region.

test/Analysis/casts.cpp

-// RUN: %clang_analyze_cc1 -analyzer-checker=core -analyzer-store=region -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-store=region -verify %s
+
+void clang_analyzer_eval(bool);
 
 bool PR14634(int x) {
   double y = (double)x;
   return !y;
 }
 
 bool PR14634_implicit(int x) {
   double y = (double)x;
bool testCastToIntPtrRValueRef(char *p, int *s) {
   return castToIntPtrRValueRef(p) != s; // no-crash
 }
 
 bool retrievePointerFromBoolean(int *p) {
   bool q;
   *reinterpret_cast<int **>(&q) = p;
   return q;
 }
+
+namespace base_to_derived {
+struct A {};
+struct B : public A{};
+
+void foo(A* a) {
+  B* b = (B* ) a;
+  A* a2 = (A *) b;
+  clang_analyzer_eval(a2 == a); // expected-warning{{TRUE}}
+}
+}
+
+namespace base_to_derived_double_inheritance {
+struct A {
+  int x;
+};
+struct B {
+  int y;
+};
+struct C : A, B {};
+
+void foo(B *b) {
+  C *c = (C *)b;
+  b->y = 1;
+  clang_analyzer_eval(c->x); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(c->y); // expected-warning{{TRUE}}
+}
+}
+