//===--- ModuleManager.cpp - Module Manager ---------------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This file defines the ModuleManager class, which manages a set of loaded
//  modules for the ASTReader.
//
//===----------------------------------------------------------------------===//
#include "clang/Lex/HeaderSearch.h"
#include "clang/Lex/ModuleMap.h"
#include "clang/Serialization/GlobalModuleIndex.h"
#include "clang/Serialization/ModuleManager.h"
#include "llvm/Support/MemoryBuffer.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/raw_ostream.h"
#include <system_error>

#ifndef NDEBUG
#include "llvm/Support/GraphWriter.h"
#endif

using namespace clang;
using namespace serialization;

ModuleFile *ModuleManager::lookup(StringRef Name) {
  const FileEntry *Entry = FileMgr.getFile(Name, /*openFile=*/false,
                                           /*cacheFailure=*/false);
  if (Entry)
    return lookup(Entry);

  return nullptr;
}

ModuleFile *ModuleManager::lookup(const FileEntry *File) {
  llvm::DenseMap<const FileEntry *, ModuleFile *>::iterator Known
    = Modules.find(File);
  if (Known == Modules.end())
    return nullptr;

  return Known->second;
}

std::unique_ptr<llvm::MemoryBuffer>
ModuleManager::lookupBuffer(StringRef Name) {
  const FileEntry *Entry = FileMgr.getFile(Name, /*openFile=*/false,
                                           /*cacheFailure=*/false);
  return std::move(InMemoryBuffers[Entry]);
}

ModuleManager::AddModuleResult
ModuleManager::addModule(StringRef FileName, ModuleKind Type,
                         SourceLocation ImportLoc, ModuleFile *ImportedBy,
                         unsigned Generation,
                         off_t ExpectedSize, time_t ExpectedModTime,
                         ModuleFile *&Module,
                         std::string &ErrorStr) {
  Module = nullptr;

  // Look for the file entry. This only fails if the expected size or
  // modification time differ.
  const FileEntry *Entry;
  if (lookupModuleFile(FileName, ExpectedSize, ExpectedModTime, Entry)) {
    ErrorStr = "module file out of date";
    return OutOfDate;
  }

  if (!Entry && FileName != "-") {
    ErrorStr = "module file not found";
    return Missing;
  }

  // Check whether we already loaded this module, before
  ModuleFile *&ModuleEntry = Modules[Entry];
  bool NewModule = false;
  if (!ModuleEntry) {
    // Allocate a new module.
    ModuleFile *New = new ModuleFile(Type, Generation);
    New->Index = Chain.size();
    New->FileName = FileName.str();
    New->File = Entry;
    New->ImportLoc = ImportLoc;
    Chain.push_back(New);
    NewModule = true;
    ModuleEntry = New;

    New->InputFilesValidationTimestamp = 0;
    if (New->Kind == MK_Module) {
      std::string TimestampFilename = New->getTimestampFilename();
      vfs::Status Status;
      // A cached stat value would be fine as well.
      if (!FileMgr.getNoncachedStatValue(TimestampFilename, Status))
        New->InputFilesValidationTimestamp =
            Status.getLastModificationTime().toEpochTime();
    }

    // Load the contents of the module
    if (std::unique_ptr<llvm::MemoryBuffer> Buffer = lookupBuffer(FileName)) {
      // The buffer was already provided for us.
      New->Buffer = std::move(Buffer);
    } else {
      // Open the AST file.
      std::error_code ec;
      if (FileName == "-") {
        llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Buf =
            llvm::MemoryBuffer::getSTDIN();
        ec = Buf.getError();
        if (ec)
          ErrorStr = ec.message();
        else
          New->Buffer = std::move(Buf.get());
      } else {
        // Leave the FileEntry open so if it gets read again by another
        // ModuleManager it must be the same underlying file.
        // FIXME: Because FileManager::getFile() doesn't guarantee that it will
        // give us an open file, this may not be 100% reliable.
        New->Buffer = FileMgr.getBufferForFile(New->File, &ErrorStr,
                                               /*IsVolatile*/ false,
                                               /*ShouldClose*/ false);
      }
      
      if (!New->Buffer)
        return Missing;
    }
    
    // Initialize the stream
    New->StreamFile.init((const unsigned char *)New->Buffer->getBufferStart(),
                         (const unsigned char *)New->Buffer->getBufferEnd());
  }
  
  if (ImportedBy) {
    ModuleEntry->ImportedBy.insert(ImportedBy);
    ImportedBy->Imports.insert(ModuleEntry);
  } else {
    if (!ModuleEntry->DirectlyImported)
      ModuleEntry->ImportLoc = ImportLoc;
    
    ModuleEntry->DirectlyImported = true;
  }

  Module = ModuleEntry;
  return NewModule? NewlyLoaded : AlreadyLoaded;
}

void ModuleManager::removeModules(
    ModuleIterator first, ModuleIterator last,
    llvm::SmallPtrSetImpl<ModuleFile *> &LoadedSuccessfully,
    ModuleMap *modMap) {
  if (first == last)
    return;

  // Collect the set of module file pointers that we'll be removing.
  llvm::SmallPtrSet<ModuleFile *, 4> victimSet(first, last);

  // Remove any references to the now-destroyed modules.
  for (unsigned i = 0, n = Chain.size(); i != n; ++i) {
    Chain[i]->ImportedBy.remove_if([&](ModuleFile *MF) {
      return victimSet.count(MF);
    });
  }

  // Delete the modules and erase them from the various structures.
  for (ModuleIterator victim = first; victim != last; ++victim) {
    Modules.erase((*victim)->File);

    if (modMap) {
      StringRef ModuleName = (*victim)->ModuleName;
      if (Module *mod = modMap->findModule(ModuleName)) {
        mod->setASTFile(nullptr);
      }
    }

    // Files that didn't make it through ReadASTCore successfully will be
    // rebuilt (or there was an error). Invalidate them so that we can load the
    // new files that will be renamed over the old ones.
    if (LoadedSuccessfully.count(*victim) == 0)
      FileMgr.invalidateCache((*victim)->File);

    delete *victim;
  }

  // Remove the modules from the chain.
  Chain.erase(first, last);
}

void
ModuleManager::addInMemoryBuffer(StringRef FileName,
                                 std::unique_ptr<llvm::MemoryBuffer> Buffer) {

  const FileEntry *Entry =
      FileMgr.getVirtualFile(FileName, Buffer->getBufferSize(), 0);
  InMemoryBuffers[Entry] = std::move(Buffer);
}

ModuleManager::VisitState *ModuleManager::allocateVisitState() {
  // Fast path: if we have a cached state, use it.
  if (FirstVisitState) {
    VisitState *Result = FirstVisitState;
    FirstVisitState = FirstVisitState->NextState;
    Result->NextState = nullptr;
    return Result;
  }

  // Allocate and return a new state.
  return new VisitState(size());
}

void ModuleManager::returnVisitState(VisitState *State) {
  assert(State->NextState == nullptr && "Visited state is in list?");
  State->NextState = FirstVisitState;
  FirstVisitState = State;
}

void ModuleManager::setGlobalIndex(GlobalModuleIndex *Index) {
  GlobalIndex = Index;
  if (!GlobalIndex) {
    ModulesInCommonWithGlobalIndex.clear();
    return;
  }

  // Notify the global module index about all of the modules we've already
  // loaded.
  for (unsigned I = 0, N = Chain.size(); I != N; ++I) {
    if (!GlobalIndex->loadedModuleFile(Chain[I])) {
      ModulesInCommonWithGlobalIndex.push_back(Chain[I]);
    }
  }
}

void ModuleManager::moduleFileAccepted(ModuleFile *MF) {
  if (!GlobalIndex || GlobalIndex->loadedModuleFile(MF))
    return;

  ModulesInCommonWithGlobalIndex.push_back(MF);
}

ModuleManager::ModuleManager(FileManager &FileMgr)
  : FileMgr(FileMgr), GlobalIndex(), FirstVisitState(nullptr) {}

ModuleManager::~ModuleManager() {
  for (unsigned i = 0, e = Chain.size(); i != e; ++i)
    delete Chain[e - i - 1];
  delete FirstVisitState;
}

void
ModuleManager::visit(bool (*Visitor)(ModuleFile &M, void *UserData),
                     void *UserData,
                     llvm::SmallPtrSetImpl<ModuleFile *> *ModuleFilesHit) {
  // If the visitation order vector is the wrong size, recompute the order.
  if (VisitOrder.size() != Chain.size()) {
    unsigned N = size();
    VisitOrder.clear();
    VisitOrder.reserve(N);
    
    // Record the number of incoming edges for each module. When we
    // encounter a module with no incoming edges, push it into the queue
    // to seed the queue.
    SmallVector<ModuleFile *, 4> Queue;
    Queue.reserve(N);
    llvm::SmallVector<unsigned, 4> UnusedIncomingEdges;
    UnusedIncomingEdges.reserve(size());
    for (ModuleIterator M = begin(), MEnd = end(); M != MEnd; ++M) {
      if (unsigned Size = (*M)->ImportedBy.size())
        UnusedIncomingEdges.push_back(Size);
      else {
        UnusedIncomingEdges.push_back(0);
        Queue.push_back(*M);
      }
    }

    // Traverse the graph, making sure to visit a module before visiting any
    // of its dependencies.
    unsigned QueueStart = 0;
    while (QueueStart < Queue.size()) {
      ModuleFile *CurrentModule = Queue[QueueStart++];
      VisitOrder.push_back(CurrentModule);

      // For any module that this module depends on, push it on the
      // stack (if it hasn't already been marked as visited).
      for (llvm::SetVector<ModuleFile *>::iterator
             M = CurrentModule->Imports.begin(),
             MEnd = CurrentModule->Imports.end();
           M != MEnd; ++M) {
        // Remove our current module as an impediment to visiting the
        // module we depend on. If we were the last unvisited module
        // that depends on this particular module, push it into the
        // queue to be visited.
        unsigned &NumUnusedEdges = UnusedIncomingEdges[(*M)->Index];
        if (NumUnusedEdges && (--NumUnusedEdges == 0))
          Queue.push_back(*M);
      }
    }

    assert(VisitOrder.size() == N && "Visitation order is wrong?");

    delete FirstVisitState;
    FirstVisitState = nullptr;
  }

  VisitState *State = allocateVisitState();
  unsigned VisitNumber = State->NextVisitNumber++;

  // If the caller has provided us with a hit-set that came from the global
  // module index, mark every module file in common with the global module
  // index that is *not* in that set as 'visited'.
  if (ModuleFilesHit && !ModulesInCommonWithGlobalIndex.empty()) {
    for (unsigned I = 0, N = ModulesInCommonWithGlobalIndex.size(); I != N; ++I)
    {
      ModuleFile *M = ModulesInCommonWithGlobalIndex[I];
      if (!ModuleFilesHit->count(M))
        State->VisitNumber[M->Index] = VisitNumber;
    }
  }

  for (unsigned I = 0, N = VisitOrder.size(); I != N; ++I) {
    ModuleFile *CurrentModule = VisitOrder[I];
    // Should we skip this module file?
    if (State->VisitNumber[CurrentModule->Index] == VisitNumber)
      continue;

    // Visit the module.
    assert(State->VisitNumber[CurrentModule->Index] == VisitNumber - 1);
    State->VisitNumber[CurrentModule->Index] = VisitNumber;
    if (!Visitor(*CurrentModule, UserData))
      continue;

    // The visitor has requested that cut off visitation of any
    // module that the current module depends on. To indicate this
    // behavior, we mark all of the reachable modules as having been visited.
    ModuleFile *NextModule = CurrentModule;
    do {
      // For any module that this module depends on, push it on the
      // stack (if it hasn't already been marked as visited).
      for (llvm::SetVector<ModuleFile *>::iterator
             M = NextModule->Imports.begin(),
             MEnd = NextModule->Imports.end();
           M != MEnd; ++M) {
        if (State->VisitNumber[(*M)->Index] != VisitNumber) {
          State->Stack.push_back(*M);
          State->VisitNumber[(*M)->Index] = VisitNumber;
        }
      }

      if (State->Stack.empty())
        break;

      // Pop the next module off the stack.
      NextModule = State->Stack.pop_back_val();
    } while (true);
  }

  returnVisitState(State);
}

/// \brief Perform a depth-first visit of the current module.
static bool visitDepthFirst(ModuleFile &M, 
                            bool (*Visitor)(ModuleFile &M, bool Preorder, 
                                            void *UserData), 
                            void *UserData,
                            SmallVectorImpl<bool> &Visited) {
  // Preorder visitation
  if (Visitor(M, /*Preorder=*/true, UserData))
    return true;
  
  // Visit children
  for (llvm::SetVector<ModuleFile *>::iterator IM = M.Imports.begin(),
                                            IMEnd = M.Imports.end();
       IM != IMEnd; ++IM) {
    if (Visited[(*IM)->Index])
      continue;
    Visited[(*IM)->Index] = true;

    if (visitDepthFirst(**IM, Visitor, UserData, Visited))
      return true;
  }  
  
  // Postorder visitation
  return Visitor(M, /*Preorder=*/false, UserData);
}

void ModuleManager::visitDepthFirst(bool (*Visitor)(ModuleFile &M, bool Preorder, 
                                                    void *UserData), 
                                    void *UserData) {
  SmallVector<bool, 16> Visited(size(), false);
  for (unsigned I = 0, N = Chain.size(); I != N; ++I) {
    if (Visited[Chain[I]->Index])
      continue;
    Visited[Chain[I]->Index] = true;

    if (::visitDepthFirst(*Chain[I], Visitor, UserData, Visited))
      return;
  }
}

bool ModuleManager::lookupModuleFile(StringRef FileName,
                                     off_t ExpectedSize,
                                     time_t ExpectedModTime,
                                     const FileEntry *&File) {
  // Open the file immediately to ensure there is no race between stat'ing and
  // opening the file.
  File = FileMgr.getFile(FileName, /*openFile=*/true, /*cacheFailure=*/false);

  if (!File && FileName != "-") {
    return false;
  }

  if ((ExpectedSize && ExpectedSize != File->getSize()) ||
      (ExpectedModTime && ExpectedModTime != File->getModificationTime()))
    // Do not destroy File, as it may be referenced. If we need to rebuild it,
    // it will be destroyed by removeModules.
    return true;

  return false;
}

#ifndef NDEBUG
namespace llvm {
  template<>
  struct GraphTraits<ModuleManager> {
    typedef ModuleFile NodeType;
    typedef llvm::SetVector<ModuleFile *>::const_iterator ChildIteratorType;
    typedef ModuleManager::ModuleConstIterator nodes_iterator;
    
    static ChildIteratorType child_begin(NodeType *Node) {
      return Node->Imports.begin();
    }

    static ChildIteratorType child_end(NodeType *Node) {
      return Node->Imports.end();
    }
    
    static nodes_iterator nodes_begin(const ModuleManager &Manager) {
      return Manager.begin();
    }
    
    static nodes_iterator nodes_end(const ModuleManager &Manager) {
      return Manager.end();
    }
  };
  
  template<>
  struct DOTGraphTraits<ModuleManager> : public DefaultDOTGraphTraits {
    explicit DOTGraphTraits(bool IsSimple = false)
      : DefaultDOTGraphTraits(IsSimple) { }
    
    static bool renderGraphFromBottomUp() {
      return true;
    }

    std::string getNodeLabel(ModuleFile *M, const ModuleManager&) {
      return M->ModuleName;
    }
  };
}

void ModuleManager::viewGraph() {
  llvm::ViewGraph(*this, "Modules");
}
#endif