[cfe-dev] lower bound error searching for module preprocessing entities within a source range

[Tom Honermann]

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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: clang-module-find-pp-entity.patch
Type: text/x-patch
Size: 511 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20130828/a724a355/attachment.bin>