From b097a57f58672a825c99fdfb668b04e921e363b9 Mon Sep 17 00:00:00 2001
From: Ted Kremenek <kremenek@apple.com>
Date: Tue, 7 May 2013 01:18:10 +0000
Subject: [PATCH] [analyzer; alternate arrows] provide a diagnostic for
 entering a loop for the first time.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@181282 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/StaticAnalyzer/Core/BugReporter.cpp | 110 +++++++++++++++++++-----
 1 file changed, 90 insertions(+), 20 deletions(-)

diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp
index a85235c3e4..2120101ea0 100644
--- a/lib/StaticAnalyzer/Core/BugReporter.cpp
+++ b/lib/StaticAnalyzer/Core/BugReporter.cpp
@@ -1261,25 +1261,34 @@ static void reversePropagateInterestingSymbols(BugReport &R,
 // Functions for determining if a loop was executed 0 times.
 //===----------------------------------------------------------------------===//
 
-/// Return true if the terminator is a loop and the destination is the
-/// false branch.
-static bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE) {
+static bool isLoop(const Stmt *Term) {
   switch (Term->getStmtClass()) {
     case Stmt::ForStmtClass:
     case Stmt::WhileStmtClass:
     case Stmt::ObjCForCollectionStmtClass:
-      break;
+      return true;
     default:
       // Note that we intentionally do not include do..while here.
       return false;
   }
+}
 
-  // Did we take the false branch?
+static bool isJumpToFalseBranch(const BlockEdge *BE) {
   const CFGBlock *Src = BE->getSrc();
   assert(Src->succ_size() == 2);
   return (*(Src->succ_begin()+1) == BE->getDst());
 }
 
+/// Return true if the terminator is a loop and the destination is the
+/// false branch.
+static bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE) {
+  if (!isLoop(Term))
+    return false;
+
+  // Did we take the false branch?
+  return isJumpToFalseBranch(BE);
+}
+
 static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS) {
   while (SubS) {
     if (SubS == S)
@@ -1557,6 +1566,45 @@ static void addEdgeToPath(PathPieces &path,
   PrevLoc = NewLoc;
 }
 
+enum EventCategorization { EC_None, EC_EnterLoop, EC_LoopingBack };
+
+typedef llvm::DenseMap<const PathDiagnosticEventPiece *,
+                       enum EventCategorization>
+        EventCategoryMap;
+
+
+static void pruneLoopEvents(PathPieces &path, EventCategoryMap &ECM) {
+  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) {
+    if (PathDiagnosticCallPiece *call = dyn_cast<PathDiagnosticCallPiece>(*I)) {
+      pruneLoopEvents(call->path, ECM);
+      continue;
+    }
+
+    PathDiagnosticEventPiece *I_event = dyn_cast<PathDiagnosticEventPiece>(*I);
+    if (!I_event || ECM[I_event] != EC_LoopingBack)
+      continue;
+
+    PathPieces::iterator Next = I; ++Next;
+    PathDiagnosticEventPiece *Next_event = 0;
+    for ( ; Next != E ; ++Next) {
+      Next_event = dyn_cast<PathDiagnosticEventPiece>(*Next);
+      if (Next_event)
+        break;
+    }
+
+    if (Next_event) {
+      EventCategorization E = ECM[Next_event];
+      if (E == EC_EnterLoop) {
+        PathDiagnosticLocation L = I_event->getLocation();
+        PathDiagnosticLocation L_next = Next_event->getLocation();
+        if (L == L_next) {
+          path.erase(Next);
+        }
+      }
+    }
+  }
+}
+
 static bool
 GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD,
                                          PathDiagnosticBuilder &PDB,
@@ -1573,6 +1621,8 @@ GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD,
   llvm::DenseMap<const StackFrameContext *, PathDiagnosticLocation>
     PrevLocMap;
 
+  EventCategoryMap EventCategory;
+
   const ExplodedNode *NextNode = N->getFirstPred();
   while (NextNode) {
     N = NextNode;
@@ -1687,33 +1737,48 @@ GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD,
 
           addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), LC);
           PD.getActivePath().push_front(p);
+          EventCategory[p] = EC_LoopingBack;
 
           if (CS) {
             addEdgeToPath(PD.getActivePath(), PrevLoc,
                           PathDiagnosticLocation::createEndBrace(CS, SM), LC);
           }
         }
-        
+
         const CFGBlock *BSrc = BE->getSrc();
         ParentMap &PM = PDB.getParentMap();
 
         if (const Stmt *Term = BSrc->getTerminator()) {
           // Are we jumping past the loop body without ever executing the
           // loop (because the condition was false)?
-          if (isLoopJumpPastBody(Term, &*BE) &&
-              !isInLoopBody(PM,
-                            getStmtBeforeCond(PM,
-                                              BSrc->getTerminatorCondition(),
-                                              N),
-                            Term))
-          {
-            PathDiagnosticLocation L(Term, SM, PDB.LC);
-            PathDiagnosticEventPiece *PE =
-              new PathDiagnosticEventPiece(L, "Loop body executed 0 times");
-            PE->setPrunable(true);
-            addEdgeToPath(PD.getActivePath(), PrevLoc,
-                          PE->getLocation(), LC);
-            PD.getActivePath().push_front(PE);
+          if (isLoop(Term)) {
+            const Stmt *TermCond = BSrc->getTerminatorCondition();
+            bool IsInLoopBody =
+              isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term);
+
+            const char *str = 0;
+            enum EventCategorization EC = EC_None;
+
+            if (isJumpToFalseBranch(&*BE)) {
+              if (!IsInLoopBody) {
+                str = "Loop body executed 0 times";
+              }
+            }
+            else {
+              str = "Entering loop body";
+              EC = EC_EnterLoop;
+            }
+
+            if (str) {
+              PathDiagnosticLocation L(Term, SM, PDB.LC);
+              PathDiagnosticEventPiece *PE =
+                new PathDiagnosticEventPiece(L, str);
+              EventCategory[PE] = EC;
+              PE->setPrunable(true);
+              addEdgeToPath(PD.getActivePath(), PrevLoc,
+                            PE->getLocation(), LC);
+              PD.getActivePath().push_front(PE);
+            }
           }
         }
         break;
@@ -1735,6 +1800,11 @@ GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD,
     }
   }
 
+  if (report->isValid()) {
+    // Prune redundant loop diagnostics.
+    pruneLoopEvents(PD.getMutablePieces(), EventCategory);
+  }
+
   return report->isValid();
 }
 
-- 
2.40.0