1 files changed, 114 insertions, 12 deletions

diff --git a/clang/lib/StaticAnalyzer/Checkers/PointerSubChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/PointerSubChecker.cpp
index 2438cf30b39b..eea93a41f138 100644
--- a/clang/lib/StaticAnalyzer/Checkers/PointerSubChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/PointerSubChecker.cpp
@@ -17,6 +17,7 @@
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
 #include "llvm/ADT/StringRef.h"
 
 using namespace clang;
@@ -26,16 +27,85 @@ namespace {
 class PointerSubChecker
   : public Checker< check::PreStmt<BinaryOperator> > {
   const BugType BT{this, "Pointer subtraction"};
+  const llvm::StringLiteral Msg_MemRegionDifferent =
+      "Subtraction of two pointers that do not point into the same array "
+      "is undefined behavior.";
+  const llvm::StringLiteral Msg_LargeArrayIndex =
+      "Using an array index greater than the array size at pointer subtraction "
+      "is undefined behavior.";
+  const llvm::StringLiteral Msg_NegativeArrayIndex =
+      "Using a negative array index at pointer subtraction "
+      "is undefined behavior.";
+  const llvm::StringLiteral Msg_BadVarIndex =
+      "Indexing the address of a variable with other than 1 at this place "
+      "is undefined behavior.";
+
+  bool checkArrayBounds(CheckerContext &C, const Expr *E,
+                        const ElementRegion *ElemReg,
+                        const MemRegion *Reg) const;
 
 public:
   void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const;
 };
 }
 
+bool PointerSubChecker::checkArrayBounds(CheckerContext &C, const Expr *E,
+                                         const ElementRegion *ElemReg,
+                                         const MemRegion *Reg) const {
+  if (!ElemReg)
+    return true;
+
+  auto ReportBug = [&](const llvm::StringLiteral &Msg) {
+    if (ExplodedNode *N = C.generateNonFatalErrorNode()) {
+      auto R = std::make_unique<PathSensitiveBugReport>(BT, Msg, N);
+      R->addRange(E->getSourceRange());
+      C.emitReport(std::move(R));
+    }
+  };
+
+  ProgramStateRef State = C.getState();
+  const MemRegion *SuperReg = ElemReg->getSuperRegion();
+  SValBuilder &SVB = C.getSValBuilder();
+
+  if (SuperReg == Reg) {
+    if (const llvm::APSInt *I = SVB.getKnownValue(State, ElemReg->getIndex());
+        I && (!I->isOne() && !I->isZero()))
+      ReportBug(Msg_BadVarIndex);
+    return false;
+  }
+
+  DefinedOrUnknownSVal ElemCount =
+      getDynamicElementCount(State, SuperReg, SVB, ElemReg->getElementType());
+  auto IndexTooLarge = SVB.evalBinOp(C.getState(), BO_GT, ElemReg->getIndex(),
+                                     ElemCount, SVB.getConditionType())
+                           .getAs<DefinedOrUnknownSVal>();
+  if (IndexTooLarge) {
+    ProgramStateRef S1, S2;
+    std::tie(S1, S2) = C.getState()->assume(*IndexTooLarge);
+    if (S1 && !S2) {
+      ReportBug(Msg_LargeArrayIndex);
+      return false;
+    }
+  }
+  auto IndexTooSmall = SVB.evalBinOp(State, BO_LT, ElemReg->getIndex(),
+                                     SVB.makeZeroVal(SVB.getArrayIndexType()),
+                                     SVB.getConditionType())
+                           .getAs<DefinedOrUnknownSVal>();
+  if (IndexTooSmall) {
+    ProgramStateRef S1, S2;
+    std::tie(S1, S2) = State->assume(*IndexTooSmall);
+    if (S1 && !S2) {
+      ReportBug(Msg_NegativeArrayIndex);
+      return false;
+    }
+  }
+  return true;
+}
+
 void PointerSubChecker::checkPreStmt(const BinaryOperator *B,
                                      CheckerContext &C) const {
   // When doing pointer subtraction, if the two pointers do not point to the
-  // same memory chunk, emit a warning.
+  // same array, emit a warning.
   if (B->getOpcode() != BO_Sub)
     return;
 
@@ -44,26 +114,58 @@ void PointerSubChecker::checkPreStmt(const BinaryOperator *B,
 
   const MemRegion *LR = LV.getAsRegion();
   const MemRegion *RR = RV.getAsRegion();
-
-  if (!(LR && RR))
+  if (!LR || !RR)
     return;
 
-  const MemRegion *BaseLR = LR->getBaseRegion();
-  const MemRegion *BaseRR = RR->getBaseRegion();
+  // Allow subtraction of identical pointers.
+  if (LR == RR)
+    return;
 
-  if (BaseLR == BaseRR)
+  // No warning if one operand is unknown.
+  if (isa<SymbolicRegion>(LR) || isa<SymbolicRegion>(RR))
     return;
 
-  // Allow arithmetic on different symbolic regions.
-  if (isa<SymbolicRegion>(BaseLR) || isa<SymbolicRegion>(BaseRR))
+  const auto *ElemLR = dyn_cast<ElementRegion>(LR);
+  const auto *ElemRR = dyn_cast<ElementRegion>(RR);
+
+  if (!checkArrayBounds(C, B->getLHS(), ElemLR, RR))
     return;
+  if (!checkArrayBounds(C, B->getRHS(), ElemRR, LR))
+    return;
+
+  const ValueDecl *DiffDeclL = nullptr;
+  const ValueDecl *DiffDeclR = nullptr;
+
+  if (ElemLR && ElemRR) {
+    const MemRegion *SuperLR = ElemLR->getSuperRegion();
+    const MemRegion *SuperRR = ElemRR->getSuperRegion();
+    if (SuperLR == SuperRR)
+      return;
+    // Allow arithmetic on different symbolic regions.
+    if (isa<SymbolicRegion>(SuperLR) || isa<SymbolicRegion>(SuperRR))
+      return;
+    if (const auto *SuperDLR = dyn_cast<DeclRegion>(SuperLR))
+      DiffDeclL = SuperDLR->getDecl();
+    if (const auto *SuperDRR = dyn_cast<DeclRegion>(SuperRR))
+      DiffDeclR = SuperDRR->getDecl();
+  }
 
   if (ExplodedNode *N = C.generateNonFatalErrorNode()) {
-    constexpr llvm::StringLiteral Msg =
-        "Subtraction of two pointers that do not point to the same memory "
-        "chunk may cause incorrect result.";
-    auto R = std::make_unique<PathSensitiveBugReport>(BT, Msg, N);
+    auto R =
+        std::make_unique<PathSensitiveBugReport>(BT, Msg_MemRegionDifferent, N);
     R->addRange(B->getSourceRange());
+    // The declarations may be identical even if the regions are different:
+    //   struct { int array[10]; } a, b;
+    //   do_something(&a.array[5] - &b.array[5]);
+    // In this case don't emit notes.
+    if (DiffDeclL != DiffDeclR) {
+      if (DiffDeclL)
+        R->addNote("Array at the left-hand side of subtraction",
+                   {DiffDeclL, C.getSourceManager()});
+      if (DiffDeclR)
+        R->addNote("Array at the right-hand side of subtraction",
+                   {DiffDeclR, C.getSourceManager()});
+    }
     C.emitReport(std::move(R));
   }
 }