lower bound error searching for module preprocessing entities within a source range

Attached is a patch to correct a lower bound search error that occurs when searching for module preprocessing entities within a source range.

The test case I've been using for this is:

$ cat t.c
#if __GNUC__
#endif
void f(void) {
}

The problem I was having was that a query for macro expansions occurring within the definition of f() (source range 3:1-4:1) was returning the expansion of __GNUC__ occurring at line 1:5. Clearly, no expansions should be found for that source range.

The problem was due to lines 4315-4316 below. The loop progressively reduces a half open range indicated by [First,First+Count) with PPI pointing to an element in the middle of that range. Note that PPI is always dereferenceable - it is not a past-the-end iterator (indeed, it is unconditionally dereferenced at line 4313).

If all of the source locations for the preprocessed entities precede the specified source location, then the loop will exit with PPI pointing to the last element in the range [pp_begin,pp_end). However, the intention is that, if all entities precede the specified source location, then PPI is expected to point to pp_end (a past-the-end iterator) when the loop exits (see line 4322). When the loop exits with PPI not set to pp_end, then it is interpreted as pointing to the first preprocessed entity with a source location following the specified location. This is why my query is incorrectly including the preceding macro expansion.

The attached patch against trunk (revision 189518) modifies lines 4315-4316 to first increment PPI, and then to assign First to PPI. This causes PPI to be advanced appropriately to satisfy the comparison at line 4322 when all entities precede the specified source location.

I looked for a simple way to provide a test for this behavior, but I wasn't able to find one. It seems there may be some way to test this with c-index-test, but I wasn't able to figure out a way to do so (the problem only occurs when the relevant code is loaded from a PCH file). I'm afraid I'm not very familiar with the existing tests. I did run the Clang test suite (make test) and no regressions were reported.

lib/Serialization/ASTReader.cpp:
4280 /// \brief Returns the first preprocessed entity ID that ends after \arg BLoc.
4281 PreprocessedEntityID
4282 ASTReader::findBeginPreprocessedEntity(SourceLocation BLoc) const {
4283 if (SourceMgr.isLocalSourceLocation(BLoc))
4284 return getTotalNumPreprocessedEntities();
4285
4286 GlobalSLocOffsetMapType::const_iterator
4287 SLocMapI = GlobalSLocOffsetMap.find(SourceManager::MaxLoadedOffset -
4288 BLoc.getOffset() - 1);
4289 assert(SLocMapI != GlobalSLocOffsetMap.end() &&
4290 "Corrupted global sloc offset map");
4291
4292 if (SLocMapI->second->NumPreprocessedEntities == 0)
4293 return findNextPreprocessedEntity(SLocMapI);
4294
4295 ModuleFile &M = *SLocMapI->second;
4296 typedef const PPEntityOffset *pp_iterator;
4297 pp_iterator pp_begin = M.PreprocessedEntityOffsets;
4298 pp_iterator pp_end = pp_begin + M.NumPreprocessedEntities;
4299
4300 size_t Count = M.NumPreprocessedEntities;
4301 size_t Half;
4302 pp_iterator First = pp_begin;
4303 pp_iterator PPI;
4304
4305 // Do a binary search manually instead of using std::lower_bound because
4306 // The end locations of entities may be unordered (when a macro expansion
4307 // is inside another macro argument), but for this case it is not important
4308 // whether we get the first macro expansion or its containing macro.
4309 while (Count > 0) {
4310 Half = Count/2;
4311 PPI = First;
4312 std::advance(PPI, Half);
4313 if (SourceMgr.isBeforeInTranslationUnit(ReadSourceLocation(M, PPI->End),
4314 BLoc)){
4315 First = PPI;
4316 ++First;
4317 Count = Count - Half - 1;
4318 } else
4319 Count = Half;
4320 }
4321
4322 if (PPI == pp_end)
4323 return findNextPreprocessedEntity(SLocMapI);
4324
4325 return M.BasePreprocessedEntityID + (PPI - pp_begin);
4326 }

Tom.

clang-module-find-pp-entity.patch (511 Bytes)

Could someone please review/comment/commit this patch?

Tom.

clang-module-find-pp-entity.patch (511 Bytes)

Is it possible to write a test for this?