//===- PreprocessingRecord.cpp - Record of Preprocessing ------------------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

//  This file implements the PreprocessingRecord class, which maintains a record

//  of what occurred during preprocessing, and its helpers.

//

//===----------------------------------------------------------------------===//

#include "clang/Lex/PreprocessingRecord.h"

#include "clang/Basic/IdentifierTable.h"

#include "clang/Basic/LLVM.h"

#include "clang/Basic/SourceLocation.h"

#include "clang/Basic/SourceManager.h"

#include "clang/Basic/TokenKinds.h"

#include "clang/Lex/MacroInfo.h"

#include "clang/Lex/Token.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/Optional.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/ADT/iterator_range.h"

#include "llvm/Support/Capacity.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/ErrorHandling.h"

#include <algorithm>

#include <cassert>

#include <cstddef>

#include <cstring>

#include <iterator>

#include <utility>

#include <vector>

using namespace clang;

ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() =

    default;

InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,

                                       InclusionKind Kind, StringRef FileName,

                                       bool InQuotes, bool ImportedModule,

                                       const FileEntry *File, SourceRange Range)

    : PreprocessingDirective(InclusionDirectiveKind, Range), InQuotes(InQuotes),

      Kind(Kind), ImportedModule(ImportedModule), File(File) {

  char *Memory = (char *)PPRec.Allocate(FileName.size() + 1, alignof(char));

  memcpy(Memory, FileName.data(), FileName.size());

  Memory[FileName.size()] = 0;

  this->FileName = StringRef(Memory, FileName.size());

}

PreprocessingRecord::PreprocessingRecord(SourceManager &SM) : SourceMgr(SM) {}

/// Returns a pair of [Begin, End) iterators of preprocessed entities

/// that source range \p Range encompasses.

llvm::iterator_range<PreprocessingRecord::iterator>

PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {

  if (Range.isInvalid())

    return llvm::make_range(iterator(), iterator());

  if (CachedRangeQuery.Range == Range) {

    return llvm::make_range(iterator(this, CachedRangeQuery.Result.first),

                            iterator(this, CachedRangeQuery.Result.second));

  }

  std::pair<int, int> Res = getPreprocessedEntitiesInRangeSlow(Range);

  CachedRangeQuery.Range = Range;

  CachedRangeQuery.Result = Res;

  return llvm::make_range(iterator(this, Res.first),

                          iterator(this, Res.second));

}

static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,

                                           SourceManager &SM) {

  assert(FID.isValid());

  if (!PPE)

    return false;

  SourceLocation Loc = PPE->getSourceRange().getBegin();

  if (Loc.isInvalid())

    return false;

  return SM.isInFileID(SM.getFileLoc(Loc), FID);

}

/// Returns true if the preprocessed entity that \arg PPEI iterator

/// points to is coming from the file \arg FID.

///

/// Can be used to avoid implicit deserializations of preallocated

/// preprocessed entities if we only care about entities of a specific file

/// and not from files \#included in the range given at

/// \see getPreprocessedEntitiesInRange.

bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {

  if (FID.isInvalid())

    return false;

  int Pos = std::distance(iterator(this, 0), PPEI);

  if (Pos < 0) {

    if (unsigned(-Pos-1) >= LoadedPreprocessedEntities.size()) {

      assert(0 && "Out-of bounds loaded preprocessed entity");

      return false;

    }

    assert(ExternalSource && "No external source to load from");

    unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos;

    if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex])

      return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr);

    // See if the external source can see if the entity is in the file without

    // deserializing it.

    Optional<bool> IsInFile =

        ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);

    if (IsInFile.hasValue())

      return IsInFile.getValue();

    // The external source did not provide a definite answer, go and deserialize

    // the entity to check it.

    return isPreprocessedEntityIfInFileID(

                                       getLoadedPreprocessedEntity(LoadedIndex),

                                          FID, SourceMgr);

  }

  if (unsigned(Pos) >= PreprocessedEntities.size()) {

    assert(0 && "Out-of bounds local preprocessed entity");

    return false;

  }

  return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos],

                                        FID, SourceMgr);

}

/// Returns a pair of [Begin, End) iterators of preprocessed entities

/// that source range \arg R encompasses.

std::pair<int, int>

PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {

  assert(Range.isValid());

  assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));

  std::pair<unsigned, unsigned>

    Local = findLocalPreprocessedEntitiesInRange(Range);

  // Check if range spans local entities.

  if (!ExternalSource || 
SourceMgr.isLocalSourceLocation(Range.getBegin())900
)

    return std::make_pair(Local.first, Local.second);

  std::pair<unsigned, unsigned>

    Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);

  // Check if range spans local entities.

  if (Loaded.first == Loaded.second)

    return std::make_pair(Local.first, Local.second);

  unsigned TotalLoaded = LoadedPreprocessedEntities.size();

  // Check if range spans loaded entities.

  if (Local.first == Local.second)

    return std::make_pair(int(Loaded.first)-TotalLoaded,

                          int(Loaded.second)-TotalLoaded);

  // Range spands loaded and local entities.

  return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);

}

std::pair<unsigned, unsigned>

PreprocessingRecord::findLocalPreprocessedEntitiesInRange(

                                                      SourceRange Range) const {

  if (Range.isInvalid())

    return std::make_pair(0,0);

  assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));

  unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());

  unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());

  return std::make_pair(Begin, End);

}

namespace {

template <SourceLocation (SourceRange::*getRangeLoc)() const>

struct PPEntityComp {

  const SourceManager &SM;

  explicit PPEntityComp(const SourceManager &SM) : SM(SM) {}

  bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {

    SourceLocation LHS = getLoc(L);

    SourceLocation RHS = getLoc(R);

    return SM.isBeforeInTranslationUnit(LHS, RHS);

  }

  bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {

    SourceLocation LHS = getLoc(L);

    return SM.isBeforeInTranslationUnit(LHS, RHS);

  }

  bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {

    SourceLocation RHS = getLoc(R);

    return SM.isBeforeInTranslationUnit(LHS, RHS);

  }

  SourceLocation getLoc(PreprocessedEntity *PPE) const {

    SourceRange Range = PPE->getSourceRange();

    return (Range.*getRangeLoc)();

  }

};

} // namespace

unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(

                                                     SourceLocation Loc) const {

  if (SourceMgr.isLoadedSourceLocation(Loc))

    return 0;

  size_t Count = PreprocessedEntities.size();

  size_t Half;

  std::vector<PreprocessedEntity *>::const_iterator

    First = PreprocessedEntities.begin();

  std::vector<PreprocessedEntity *>::const_iterator I;

  // 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;

    I = First;

    std::advance(I, Half);

    if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),

                                            Loc)){

      First = I;

      ++First;

      Count = Count - Half - 1;

    } else

      Count = Half;

  }

  return First - PreprocessedEntities.begin();

}

unsigned

PreprocessingRecord::findEndLocalPreprocessedEntity(SourceLocation Loc) const {

  if (SourceMgr.isLoadedSourceLocation(Loc))

    return 0;

  auto I = llvm::upper_bound(PreprocessedEntities, Loc,

                             PPEntityComp<&SourceRange::getBegin>(SourceMgr));

  return I - PreprocessedEntities.begin();

}

PreprocessingRecord::PPEntityID

PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {

  assert(Entity);

  SourceLocation BeginLoc = Entity->getSourceRange().getBegin();

  if (isa<MacroDefinitionRecord>(Entity)) {

    assert((PreprocessedEntities.empty() ||

            !SourceMgr.isBeforeInTranslationUnit(

                BeginLoc,

                PreprocessedEntities.back()->getSourceRange().getBegin())) &&

           "a macro definition was encountered out-of-order");

    PreprocessedEntities.push_back(Entity);

    return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);

  }

  // Check normal case, this entity begin location is after the previous one.

  if (PreprocessedEntities.empty() ||

      !SourceMgr.isBeforeInTranslationUnit(BeginLoc,

                   PreprocessedEntities.back()->getSourceRange().getBegin())) {

    PreprocessedEntities.push_back(Entity);

    return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);

  }

  // The entity's location is not after the previous one; this can happen with

  // include directives that form the filename using macros, e.g:

  // "#include MACRO(STUFF)"

  // or with macro expansions inside macro arguments where the arguments are

  // not expanded in the same order as listed, e.g:

  // \code

  //  #define M1 1

  //  #define M2 2

  //  #define FM(x,y) y x

  //  FM(M1, M2)

  // \endcode

  using pp_iter = std::vector<PreprocessedEntity *>::iterator;

  // Usually there are few macro expansions when defining the filename, do a

  // linear search for a few entities.

  unsigned count = 0;

  for (pp_iter RI    = PreprocessedEntities.end(),

               Begin = PreprocessedEntities.begin();

       RI != Begin && count < 4; 
--RI, ++count4
) {

    pp_iter I = RI;

    --I;

    if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,

                                           (*I)->getSourceRange().getBegin())) {

      pp_iter insertI = PreprocessedEntities.insert(RI, Entity);

      return getPPEntityID(insertI - PreprocessedEntities.begin(),

                           /*isLoaded=*/false);

    }

  }

  // Linear search unsuccessful. Do a binary search.

  pp_iter I =

      llvm::upper_bound(PreprocessedEntities, BeginLoc,

                        PPEntityComp<&SourceRange::getBegin>(SourceMgr));

  pp_iter insertI = PreprocessedEntities.insert(I, Entity);

  return getPPEntityID(insertI - PreprocessedEntities.begin(),

                       /*isLoaded=*/false);

}

void PreprocessingRecord::SetExternalSource(

                                    ExternalPreprocessingRecordSource &Source) {

  assert(!ExternalSource &&

         "Preprocessing record already has an external source");

  ExternalSource = &Source;

}

unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {

  unsigned Result = LoadedPreprocessedEntities.size();

  LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()

                                    + NumEntities);

  return Result;

}

unsigned PreprocessingRecord::allocateSkippedRanges(unsigned NumRanges) {

  unsigned Result = SkippedRanges.size();

  SkippedRanges.resize(SkippedRanges.size() + NumRanges);

  SkippedRangesAllLoaded = false;

  return Result;

}

void PreprocessingRecord::ensureSkippedRangesLoaded() {

  if (SkippedRangesAllLoaded || 
!ExternalSource14
)

    return;

  
for (unsigned Index = 0; 14
Index != SkippedRanges.size(); 
++Index36
) {

    if (SkippedRanges[Index].isInvalid())

      SkippedRanges[Index] = ExternalSource->ReadSkippedRange(Index);

  }

  SkippedRangesAllLoaded = true;

}

void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,

                                                  MacroDefinitionRecord *Def) {

  MacroDefinitions[Macro] = Def;

}

/// Retrieve the preprocessed entity at the given ID.

PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){

  if (PPID.ID < 0) {

    unsigned Index = -PPID.ID - 1;

    assert(Index < LoadedPreprocessedEntities.size() &&

           "Out-of bounds loaded preprocessed entity");

    return getLoadedPreprocessedEntity(Index);

  }

  if (PPID.ID == 0)

    return nullptr;

  unsigned Index = PPID.ID - 1;

  assert(Index < PreprocessedEntities.size() &&

         "Out-of bounds local preprocessed entity");

  return PreprocessedEntities[Index];

}

/// Retrieve the loaded preprocessed entity at the given index.

PreprocessedEntity *

PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {

  assert(Index < LoadedPreprocessedEntities.size() &&

         "Out-of bounds loaded preprocessed entity");

  assert(ExternalSource && "No external source to load from");

  PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];

  if (!Entity) {

    Entity = ExternalSource->ReadPreprocessedEntity(Index);

    if (!Entity) // Failed to load.

      Entity = new (*this)

         PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());

  }

  return Entity;

}

MacroDefinitionRecord *

PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {

  llvm::DenseMap<const MacroInfo *, MacroDefinitionRecord *>::iterator Pos =

      MacroDefinitions.find(MI);

  if (Pos == MacroDefinitions.end())

    return nullptr;

  return Pos->second;

}

void PreprocessingRecord::addMacroExpansion(const Token &Id,

                                            const MacroInfo *MI,

                                            SourceRange Range) {

  // We don't record nested macro expansions.

  if (Id.getLocation().isMacroID())

    return;

  if (MI->isBuiltinMacro())

    addPreprocessedEntity(new (*this)

                              MacroExpansion(Id.getIdentifierInfo(), Range));

  else if (MacroDefinitionRecord *Def = findMacroDefinition(MI))

    addPreprocessedEntity(new (*this) MacroExpansion(Def, Range));

}

void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok,

                                const MacroDefinition &MD) {

  // This is not actually a macro expansion but record it as a macro reference.

  if (MD)

    addMacroExpansion(MacroNameTok, MD.getMacroInfo(),

                      MacroNameTok.getLocation());

}

void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok,

                                 const MacroDefinition &MD) {

  // This is not actually a macro expansion but record it as a macro reference.

  if (MD)

    addMacroExpansion(MacroNameTok, MD.getMacroInfo(),

                      MacroNameTok.getLocation());

}

void PreprocessingRecord::Defined(const Token &MacroNameTok,

                                  const MacroDefinition &MD,

                                  SourceRange Range) {

  // This is not actually a macro expansion but record it as a macro reference.

  if (MD)

    addMacroExpansion(MacroNameTok, MD.getMacroInfo(),

                      MacroNameTok.getLocation());

}

void PreprocessingRecord::SourceRangeSkipped(SourceRange Range,

                                             SourceLocation EndifLoc) {

  assert(Range.isValid());

  SkippedRanges.emplace_back(Range.getBegin(), EndifLoc);

}

void PreprocessingRecord::MacroExpands(const Token &Id,

                                       const MacroDefinition &MD,

                                       SourceRange Range,

                                       const MacroArgs *Args) {

  addMacroExpansion(Id, MD.getMacroInfo(), Range);

}

void PreprocessingRecord::MacroDefined(const Token &Id,

                                       const MacroDirective *MD) {

  const MacroInfo *MI = MD->getMacroInfo();

  SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());

  MacroDefinitionRecord *Def =

      new (*this) MacroDefinitionRecord(Id.getIdentifierInfo(), R);

  addPreprocessedEntity(Def);

  MacroDefinitions[MI] = Def;

}

void PreprocessingRecord::MacroUndefined(const Token &Id,

                                         const MacroDefinition &MD,

                                         const MacroDirective *Undef) {

  MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); });

}

void PreprocessingRecord::InclusionDirective(

    SourceLocation HashLoc,

    const Token &IncludeTok,

    StringRef FileName,

    bool IsAngled,

    CharSourceRange FilenameRange,

    const FileEntry *File,

    StringRef SearchPath,

    StringRef RelativePath,

    const Module *Imported,

    SrcMgr::CharacteristicKind FileType) {

  InclusionDirective::InclusionKind Kind = InclusionDirective::Include;

  switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {

  case tok::pp_include:

    Kind = InclusionDirective::Include;

    break;

  case tok::pp_import:

    Kind = InclusionDirective::Import;

    break;

  case tok::pp_include_next:

    Kind = InclusionDirective::IncludeNext;

    break;

  case tok::pp___include_macros:

    Kind = InclusionDirective::IncludeMacros;

    break;

  default:

    llvm_unreachable("Unknown include directive kind");

  }

  SourceLocation EndLoc;

  if (!IsAngled) {

    EndLoc = FilenameRange.getBegin();

  } else {

    EndLoc = FilenameRange.getEnd();

    if (FilenameRange.isCharRange())

      EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects

                                            // a token range.

  }

  clang::InclusionDirective *ID =

      new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,

                                            (bool)Imported, File,

                                            SourceRange(HashLoc, EndLoc));

  addPreprocessedEntity(ID);

}

size_t PreprocessingRecord::getTotalMemory() const {

  return BumpAlloc.getTotalMemory()

    + llvm::capacity_in_bytes(MacroDefinitions)

    + llvm::capacity_in_bytes(PreprocessedEntities)

    + llvm::capacity_in_bytes(LoadedPreprocessedEntities)

    + llvm::capacity_in_bytes(SkippedRanges);

}