Attempt to make the PathDiagnostic emission order more deterministic by
looking at PathPieces.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@163427 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/StaticAnalyzer/Core/PathDiagnostic.cpp b/lib/StaticAnalyzer/Core/PathDiagnostic.cpp
index d010a66..15a6635 100644
--- a/lib/StaticAnalyzer/Core/PathDiagnostic.cpp
+++ b/lib/StaticAnalyzer/Core/PathDiagnostic.cpp
@@ -208,6 +208,41 @@
 
 
 namespace {
+  
+static llvm::Optional<bool> comparePiece(PathDiagnosticPiece &X,
+                                         PathDiagnosticPiece &Y) {
+  PathDiagnosticPiece::Kind XK = X.getKind(), YK = Y.getKind();
+  if (XK != YK) {
+    return XK < YK;
+  }
+  FullSourceLoc XL = X.getLocation().asLocation();
+  FullSourceLoc YL = Y.getLocation().asLocation();
+  if (XL < YL)
+    return true;
+  if (YL < XL)
+    return false;
+  const std::string &XS = X.getString();
+  const std::string &YS = Y.getString();
+  if (XS != YS)
+    return XS < YS;
+  return llvm::Optional<bool>();
+}
+  
+static bool comparePathPieces(const PathPieces &X, const PathPieces &Y) {
+  if (X.size() < Y.size())
+    return true;
+  if (X.size() > Y.size())
+    return false;
+  // Compare individual parts of the path.
+  assert(X.size() == Y.size());
+  for (unsigned i = 0, n = X.size(); i < n; ++i) {
+    llvm::Optional<bool> B = comparePiece(*X[i], *Y[i]);
+    if (B.hasValue())
+      return B.getValue();
+  }
+  return false;
+}
+  
 struct CompareDiagnostics {
   // Compare if 'X' is "<" than 'Y'.
   bool operator()(const PathDiagnostic *X, const PathDiagnostic *Y) const {
@@ -216,7 +251,7 @@
     const FullSourceLoc &YLoc = Y->getLocation().asLocation();
     if (XLoc < YLoc)
       return true;
-    if (XLoc != YLoc)
+    if (YLoc < XLoc)
       return false;
     
     // Next, compare by bug type.
@@ -235,8 +270,8 @@
     if (XDesc != YDesc)
       return false;
     
-    // FIXME: Further refine by comparing PathDiagnosticPieces?
-    return false;    
+    // Fall back to comparing path pieces.
+    return comparePathPieces(X->path, Y->path);
   }  
 };  
 }
diff --git a/test/Analysis/retain-release.m b/test/Analysis/retain-release.m
index 9638d64..ee71124 100644
--- a/test/Analysis/retain-release.m
+++ b/test/Analysis/retain-release.m
@@ -1924,7 +1924,6 @@
 }
 
 // CHECK: <plist version="1.0">
-// CHECK: <dict>
 // CHECK:  <key>diagnostics</key>
 // CHECK-NEXT:  <array>
 // CHECK-NEXT:   <dict>
@@ -12752,10 +12751,44 @@
 // CHECK-NEXT:    <key>path</key>
 // CHECK-NEXT:    <array>
 // CHECK-NEXT:     <dict>
+// CHECK-NEXT:      <key>kind</key><string>control</string>
+// CHECK-NEXT:      <key>edges</key>
+// CHECK-NEXT:       <array>
+// CHECK-NEXT:        <dict>
+// CHECK-NEXT:         <key>start</key>
+// CHECK-NEXT:          <array>
+// CHECK-NEXT:           <dict>
+// CHECK-NEXT:            <key>line</key><integer>838</integer>
+// CHECK-NEXT:            <key>col</key><integer>3</integer>
+// CHECK-NEXT:            <key>file</key><integer>0</integer>
+// CHECK-NEXT:           </dict>
+// CHECK-NEXT:           <dict>
+// CHECK-NEXT:            <key>line</key><integer>838</integer>
+// CHECK-NEXT:            <key>col</key><integer>3</integer>
+// CHECK-NEXT:            <key>file</key><integer>0</integer>
+// CHECK-NEXT:           </dict>
+// CHECK-NEXT:          </array>
+// CHECK-NEXT:         <key>end</key>
+// CHECK-NEXT:          <array>
+// CHECK-NEXT:           <dict>
+// CHECK-NEXT:            <key>line</key><integer>839</integer>
+// CHECK-NEXT:            <key>col</key><integer>3</integer>
+// CHECK-NEXT:            <key>file</key><integer>0</integer>
+// CHECK-NEXT:           </dict>
+// CHECK-NEXT:           <dict>
+// CHECK-NEXT:            <key>line</key><integer>839</integer>
+// CHECK-NEXT:            <key>col</key><integer>3</integer>
+// CHECK-NEXT:            <key>file</key><integer>0</integer>
+// CHECK-NEXT:           </dict>
+// CHECK-NEXT:          </array>
+// CHECK-NEXT:        </dict>
+// CHECK-NEXT:       </array>
+// CHECK-NEXT:     </dict>
+// CHECK-NEXT:     <dict>
 // CHECK-NEXT:      <key>kind</key><string>event</string>
 // CHECK-NEXT:      <key>location</key>
 // CHECK-NEXT:      <dict>
-// CHECK-NEXT:       <key>line</key><integer>838</integer>
+// CHECK-NEXT:       <key>line</key><integer>839</integer>
 // CHECK-NEXT:       <key>col</key><integer>3</integer>
 // CHECK-NEXT:       <key>file</key><integer>0</integer>
 // CHECK-NEXT:      </dict>
@@ -12763,12 +12796,12 @@
 // CHECK-NEXT:      <array>
 // CHECK-NEXT:        <array>
 // CHECK-NEXT:         <dict>
-// CHECK-NEXT:          <key>line</key><integer>838</integer>
+// CHECK-NEXT:          <key>line</key><integer>839</integer>
 // CHECK-NEXT:          <key>col</key><integer>3</integer>
 // CHECK-NEXT:          <key>file</key><integer>0</integer>
 // CHECK-NEXT:         </dict>
 // CHECK-NEXT:         <dict>
-// CHECK-NEXT:          <key>line</key><integer>838</integer>
+// CHECK-NEXT:          <key>line</key><integer>839</integer>
 // CHECK-NEXT:          <key>col</key><integer>18</integer>
 // CHECK-NEXT:          <key>file</key><integer>0</integer>
 // CHECK-NEXT:         </dict>
@@ -12776,15 +12809,15 @@
 // CHECK-NEXT:      </array>
 // CHECK-NEXT:      <key>depth</key><integer>0</integer>
 // CHECK-NEXT:      <key>extended_message</key>
-// CHECK-NEXT:      <string>Calling &apos;NoCopyString&apos;</string>
+// CHECK-NEXT:      <string>Calling &apos;noCopyString&apos;</string>
 // CHECK-NEXT:      <key>message</key>
-// CHECK-NEXT: <string>Calling &apos;NoCopyString&apos;</string>
+// CHECK-NEXT: <string>Calling &apos;noCopyString&apos;</string>
 // CHECK-NEXT:     </dict>
 // CHECK-NEXT:     <dict>
 // CHECK-NEXT:      <key>kind</key><string>event</string>
 // CHECK-NEXT:      <key>location</key>
 // CHECK-NEXT:      <dict>
-// CHECK-NEXT:       <key>line</key><integer>833</integer>
+// CHECK-NEXT:       <key>line</key><integer>834</integer>
 // CHECK-NEXT:       <key>col</key><integer>1</integer>
 // CHECK-NEXT:       <key>file</key><integer>0</integer>
 // CHECK-NEXT:      </dict>
@@ -12802,12 +12835,12 @@
 // CHECK-NEXT:         <key>start</key>
 // CHECK-NEXT:          <array>
 // CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>833</integer>
+// CHECK-NEXT:            <key>line</key><integer>834</integer>
 // CHECK-NEXT:            <key>col</key><integer>1</integer>
 // CHECK-NEXT:            <key>file</key><integer>0</integer>
 // CHECK-NEXT:           </dict>
 // CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>833</integer>
+// CHECK-NEXT:            <key>line</key><integer>834</integer>
 // CHECK-NEXT:            <key>col</key><integer>1</integer>
 // CHECK-NEXT:            <key>file</key><integer>0</integer>
 // CHECK-NEXT:           </dict>
@@ -12815,12 +12848,12 @@
 // CHECK-NEXT:         <key>end</key>
 // CHECK-NEXT:          <array>
 // CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>833</integer>
+// CHECK-NEXT:            <key>line</key><integer>834</integer>
 // CHECK-NEXT:            <key>col</key><integer>30</integer>
 // CHECK-NEXT:            <key>file</key><integer>0</integer>
 // CHECK-NEXT:           </dict>
 // CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>833</integer>
+// CHECK-NEXT:            <key>line</key><integer>834</integer>
 // CHECK-NEXT:            <key>col</key><integer>35</integer>
 // CHECK-NEXT:            <key>file</key><integer>0</integer>
 // CHECK-NEXT:           </dict>
@@ -12836,12 +12869,12 @@
 // CHECK-NEXT:         <key>start</key>
 // CHECK-NEXT:          <array>
 // CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>833</integer>
+// CHECK-NEXT:            <key>line</key><integer>834</integer>
 // CHECK-NEXT:            <key>col</key><integer>30</integer>
 // CHECK-NEXT:            <key>file</key><integer>0</integer>
 // CHECK-NEXT:           </dict>
 // CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>833</integer>
+// CHECK-NEXT:            <key>line</key><integer>834</integer>
 // CHECK-NEXT:            <key>col</key><integer>35</integer>
 // CHECK-NEXT:            <key>file</key><integer>0</integer>
 // CHECK-NEXT:           </dict>
@@ -12849,12 +12882,12 @@
 // CHECK-NEXT:         <key>end</key>
 // CHECK-NEXT:          <array>
 // CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>833</integer>
+// CHECK-NEXT:            <key>line</key><integer>834</integer>
 // CHECK-NEXT:            <key>col</key><integer>37</integer>
 // CHECK-NEXT:            <key>file</key><integer>0</integer>
 // CHECK-NEXT:           </dict>
 // CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>833</integer>
+// CHECK-NEXT:            <key>line</key><integer>834</integer>
 // CHECK-NEXT:            <key>col</key><integer>37</integer>
 // CHECK-NEXT:            <key>file</key><integer>0</integer>
 // CHECK-NEXT:           </dict>
@@ -12866,7 +12899,7 @@
 // CHECK-NEXT:      <key>kind</key><string>event</string>
 // CHECK-NEXT:      <key>location</key>
 // CHECK-NEXT:      <dict>
-// CHECK-NEXT:       <key>line</key><integer>833</integer>
+// CHECK-NEXT:       <key>line</key><integer>834</integer>
 // CHECK-NEXT:       <key>col</key><integer>37</integer>
 // CHECK-NEXT:       <key>file</key><integer>0</integer>
 // CHECK-NEXT:      </dict>
@@ -12874,12 +12907,12 @@
 // CHECK-NEXT:      <array>
 // CHECK-NEXT:        <array>
 // CHECK-NEXT:         <dict>
-// CHECK-NEXT:          <key>line</key><integer>833</integer>
+// CHECK-NEXT:          <key>line</key><integer>834</integer>
 // CHECK-NEXT:          <key>col</key><integer>37</integer>
 // CHECK-NEXT:          <key>file</key><integer>0</integer>
 // CHECK-NEXT:         </dict>
 // CHECK-NEXT:         <dict>
-// CHECK-NEXT:          <key>line</key><integer>833</integer>
+// CHECK-NEXT:          <key>line</key><integer>834</integer>
 // CHECK-NEXT:          <key>col</key><integer>59</integer>
 // CHECK-NEXT:          <key>file</key><integer>0</integer>
 // CHECK-NEXT:         </dict>
@@ -12895,7 +12928,7 @@
 // CHECK-NEXT:      <key>kind</key><string>event</string>
 // CHECK-NEXT:      <key>location</key>
 // CHECK-NEXT:      <dict>
-// CHECK-NEXT:       <key>line</key><integer>838</integer>
+// CHECK-NEXT:       <key>line</key><integer>839</integer>
 // CHECK-NEXT:       <key>col</key><integer>3</integer>
 // CHECK-NEXT:       <key>file</key><integer>0</integer>
 // CHECK-NEXT:      </dict>
@@ -12903,12 +12936,12 @@
 // CHECK-NEXT:      <array>
 // CHECK-NEXT:        <array>
 // CHECK-NEXT:         <dict>
-// CHECK-NEXT:          <key>line</key><integer>838</integer>
+// CHECK-NEXT:          <key>line</key><integer>839</integer>
 // CHECK-NEXT:          <key>col</key><integer>3</integer>
 // CHECK-NEXT:          <key>file</key><integer>0</integer>
 // CHECK-NEXT:         </dict>
 // CHECK-NEXT:         <dict>
-// CHECK-NEXT:          <key>line</key><integer>838</integer>
+// CHECK-NEXT:          <key>line</key><integer>839</integer>
 // CHECK-NEXT:          <key>col</key><integer>18</integer>
 // CHECK-NEXT:          <key>file</key><integer>0</integer>
 // CHECK-NEXT:         </dict>
@@ -12916,43 +12949,9 @@
 // CHECK-NEXT:      </array>
 // CHECK-NEXT:      <key>depth</key><integer>1</integer>
 // CHECK-NEXT:      <key>extended_message</key>
-// CHECK-NEXT:      <string>Returning from &apos;NoCopyString&apos;</string>
+// CHECK-NEXT:      <string>Returning from &apos;noCopyString&apos;</string>
 // CHECK-NEXT:      <key>message</key>
-// CHECK-NEXT: <string>Returning from &apos;NoCopyString&apos;</string>
-// CHECK-NEXT:     </dict>
-// CHECK-NEXT:     <dict>
-// CHECK-NEXT:      <key>kind</key><string>control</string>
-// CHECK-NEXT:      <key>edges</key>
-// CHECK-NEXT:       <array>
-// CHECK-NEXT:        <dict>
-// CHECK-NEXT:         <key>start</key>
-// CHECK-NEXT:          <array>
-// CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>838</integer>
-// CHECK-NEXT:            <key>col</key><integer>3</integer>
-// CHECK-NEXT:            <key>file</key><integer>0</integer>
-// CHECK-NEXT:           </dict>
-// CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>838</integer>
-// CHECK-NEXT:            <key>col</key><integer>3</integer>
-// CHECK-NEXT:            <key>file</key><integer>0</integer>
-// CHECK-NEXT:           </dict>
-// CHECK-NEXT:          </array>
-// CHECK-NEXT:         <key>end</key>
-// CHECK-NEXT:          <array>
-// CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>839</integer>
-// CHECK-NEXT:            <key>col</key><integer>3</integer>
-// CHECK-NEXT:            <key>file</key><integer>0</integer>
-// CHECK-NEXT:           </dict>
-// CHECK-NEXT:           <dict>
-// CHECK-NEXT:            <key>line</key><integer>839</integer>
-// CHECK-NEXT:            <key>col</key><integer>3</integer>
-// CHECK-NEXT:            <key>file</key><integer>0</integer>
-// CHECK-NEXT:           </dict>
-// CHECK-NEXT:          </array>
-// CHECK-NEXT:        </dict>
-// CHECK-NEXT:       </array>
+// CHECK-NEXT: <string>Returning from &apos;noCopyString&apos;</string>
 // CHECK-NEXT:     </dict>
 // CHECK-NEXT:     <dict>
 // CHECK-NEXT:      <key>kind</key><string>control</string>
@@ -23804,3 +23803,4 @@
 // CHECK-NEXT:   </dict>
 // CHECK-NEXT:  </array>
 // CHECK-NEXT: </dict>
+// CHECK-NEXT: </plist>
\ No newline at end of file