Do manual binary search for preprocessing entities because their end locations

may be unordered and MSVC's debug-mode doesn't like it.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@140337 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 22 insertions, 3 deletions

diff --git a/lib/Serialization/ASTReader.cpp b/lib/Serialization/ASTReader.cpp
index 5f489d4067..f83f709ebe 100644
--- a/lib/Serialization/ASTReader.cpp
+++ b/lib/Serialization/ASTReader.cpp
@@ -2947,9 +2947,28 @@ ASTReader::findBeginPreprocessedEntity(SourceLocation BLoc) const {
   typedef const PPEntityOffset *pp_iterator;
   pp_iterator pp_begin = M.PreprocessedEntityOffsets;
   pp_iterator pp_end = pp_begin + M.NumPreprocessedEntities;
-  pp_iterator PPI =
-      std::lower_bound(pp_begin, pp_end, BLoc,
-                       PPEntityComp<&PPEntityOffset::End>(*this, M));
+
+  size_t Count = M.NumPreprocessedEntities;
+  size_t Half;
+  pp_iterator First = pp_begin;
+  pp_iterator PPI;
+
+  // Do a binary search manually instead of using std::lower_bound because
+  // The end locations of entities may be unordered (when a macro expansion
+  // is inside another macro argument), but for this case it is not important
+  // whether we get the first macro expansion or its containing macro.
+  while (Count > 0) {
+    Half = Count/2;
+    PPI = First;
+    std::advance(PPI, Half);
+    if (SourceMgr.isBeforeInTranslationUnit(ReadSourceLocation(M, PPI->End),
+                                            BLoc)){
+      First = PPI;
+      ++First;
+      Count = Count - Half - 1;
+    } else
+      Count = Half;
+  }
 
   if (PPI == pp_end)
     return findNextPreprocessedEntity(SLocMapI);