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

[Tom Honermann]

Could someone please review/comment/commit this patch?

Tom.

On 08/28/2013 06:19 PM, Tom Honermann wrote:
> 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.
>
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>
-------------- 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/20130919/7525e100/attachment.bin>