//===- MultiOnDiskHashTable.h - Merged set of hash tables -------*- C++ -*-===//

//

// 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 provides a hash table data structure suitable for incremental and

//  distributed storage across a set of files.

//

//  Multiple hash tables from different files are implicitly merged to improve

//  performance, and on reload the merged table will override those from other

//  files.

//

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

#ifndef LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H

#define LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/DenseSet.h"

#include "llvm/ADT/PointerUnion.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/TinyPtrVector.h"

#include "llvm/ADT/iterator_range.h"

#include "llvm/Support/Endian.h"

#include "llvm/Support/EndianStream.h"

#include "llvm/Support/OnDiskHashTable.h"

#include "llvm/Support/raw_ostream.h"

#include <algorithm>

#include <cstdint>

#include <vector>

namespace clang {

namespace serialization {

/// A collection of on-disk hash tables, merged when relevant for performance.

template<typename Info> class MultiOnDiskHashTable {

public:

  /// A handle to a file, used when overriding tables.

  using file_type = typename Info::file_type;

  /// A pointer to an on-disk representation of the hash table.

  using storage_type = const unsigned char *;

  using external_key_type = typename Info::external_key_type;

  using internal_key_type = typename Info::internal_key_type;

  using data_type = typename Info::data_type;

  using data_type_builder = typename Info::data_type_builder;

  using hash_value_type = unsigned;

private:

  /// The generator is permitted to read our merged table.

  template<typename ReaderInfo, typename WriterInfo>

  friend class MultiOnDiskHashTableGenerator;

  /// A hash table stored on disk.

  struct OnDiskTable {

    using HashTable = llvm::OnDiskIterableChainedHashTable<Info>;

    file_type File;

    HashTable Table;

    OnDiskTable(file_type File, unsigned NumBuckets, unsigned NumEntries,

                storage_type Buckets, storage_type Payload, storage_type Base,

                const Info &InfoObj)

        : File(File),

          Table(NumBuckets, NumEntries, Buckets, Payload, Base, InfoObj) {}

  };

  struct MergedTable {

    std::vector<file_type> Files;

    llvm::DenseMap<internal_key_type, data_type> Data;

  };

  using Table = llvm::PointerUnion<OnDiskTable *, MergedTable *>;

  using TableVector = llvm::TinyPtrVector<void *>;

  /// The current set of on-disk and merged tables.

  /// We manually store the opaque value of the Table because TinyPtrVector

  /// can't cope with holding a PointerUnion directly.

  /// There can be at most one MergedTable in this vector, and if present,

  /// it is the first table.

  TableVector Tables;

  /// Files corresponding to overridden tables that we've not yet

  /// discarded.

  llvm::TinyPtrVector<file_type> PendingOverrides;

  struct AsOnDiskTable {

    using result_type = OnDiskTable *;

    result_type operator()(void *P) const {

      return Table::getFromOpaqueValue(P).template get<OnDiskTable *>();

    }

  };

  using table_iterator =

      llvm::mapped_iterator<TableVector::iterator, AsOnDiskTable>;

  using table_range = llvm::iterator_range<table_iterator>;

  /// The current set of on-disk tables.

  table_range tables() {

    auto Begin = Tables.begin(), End = Tables.end();

    if (getMergedTable())

      ++Begin;

    return llvm::make_range(llvm::map_iterator(Begin, AsOnDiskTable()),

                            llvm::map_iterator(End, AsOnDiskTable()));

  }

  MergedTable *getMergedTable() const {

    // If we already have a merged table, it's the first one.

    return Tables.empty() ? 
nullptr740k
 : Table::getFromOpaqueValue(*Tables.begin())

                                          .template dyn_cast<MergedTable*>();

  }

  /// Delete all our current on-disk tables.

  void clear() {

    for (auto *T : tables())

      delete T;

    if (auto *M = getMergedTable())

      delete M;

    Tables.clear();

  }

  void removeOverriddenTables() {

    llvm::DenseSet<file_type> Files;

    Files.insert(PendingOverrides.begin(), PendingOverrides.end());

    // Explicitly capture Files to work around an MSVC 2015 rejects-valid bug.

    auto ShouldRemove = [&Files](void *T) -> bool {

      auto *ODT = Table::getFromOpaqueValue(T).template get<OnDiskTable *>();

      bool Remove = Files.count(ODT->File);

      if (Remove)

        delete ODT;

      return Remove;

    };

    Tables.erase(std::remove_if(tables().begin().getCurrent(), Tables.end(),

                                ShouldRemove),

                 Tables.end());

    PendingOverrides.clear();

  }

  void condense() {

    MergedTable *Merged = getMergedTable();

    if (!Merged)

      Merged = new MergedTable;

    // Read in all the tables and merge them together.

    // FIXME: Be smarter about which tables we merge.

    for (auto *ODT : tables()) {

      auto &HT = ODT->Table;

      Info &InfoObj = HT.getInfoObj();

      for (auto I = HT.data_begin(), E = HT.data_end(); I != E; 
++I18.9M
) {

        auto *LocalPtr = I.getItem();

        // FIXME: Don't rely on the OnDiskHashTable format here.

        auto L = InfoObj.ReadKeyDataLength(LocalPtr);

        const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);

        data_type_builder ValueBuilder(Merged->Data[Key]);

        InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second,

                             ValueBuilder);

      }

      Merged->Files.push_back(ODT->File);

      delete ODT;

    }

    Tables.clear();

    Tables.push_back(Table(Merged).getOpaqueValue());

  }

public:

  MultiOnDiskHashTable() = default;

  MultiOnDiskHashTable(MultiOnDiskHashTable &&O)

      : Tables(std::move(O.Tables)),

        PendingOverrides(std::move(O.PendingOverrides)) {

    O.Tables.clear();

  }

  MultiOnDiskHashTable &operator=(MultiOnDiskHashTable &&O) {

    if (&O == this)

      return *this;

    clear();

    Tables = std::move(O.Tables);

    O.Tables.clear();

    PendingOverrides = std::move(O.PendingOverrides);

    return *this;

  }

  ~MultiOnDiskHashTable() { clear(); }

  /// Add the table \p Data loaded from file \p File.

  void add(file_type File, storage_type Data, Info InfoObj = Info()) {

    using namespace llvm::support;

    storage_type Ptr = Data;

    uint32_t BucketOffset = endian::readNext<uint32_t, little, unaligned>(Ptr);

    // Read the list of overridden files.

    uint32_t NumFiles = endian::readNext<uint32_t, little, unaligned>(Ptr);

    // FIXME: Add a reserve() to TinyPtrVector so that we don't need to make

    // an additional copy.

    llvm::SmallVector<file_type, 16> OverriddenFiles;

    OverriddenFiles.reserve(NumFiles);

    for (/**/; NumFiles != 0; 
--NumFiles4.00M
)

      OverriddenFiles.push_back(InfoObj.ReadFileRef(Ptr));

    PendingOverrides.insert(PendingOverrides.end(), OverriddenFiles.begin(),

                            OverriddenFiles.end());

    // Read the OnDiskChainedHashTable header.

    storage_type Buckets = Data + BucketOffset;

    auto NumBucketsAndEntries =

        OnDiskTable::HashTable::readNumBucketsAndEntries(Buckets);

    // Register the table.

    Table NewTable = new OnDiskTable(File, NumBucketsAndEntries.first,

                                     NumBucketsAndEntries.second,

                                     Buckets, Ptr, Data, std::move(InfoObj));

    Tables.push_back(NewTable.getOpaqueValue());

  }

  /// Find and read the lookup results for \p EKey.

  data_type find(const external_key_type &EKey) {

    data_type Result;

    if (!PendingOverrides.empty())

      removeOverriddenTables();

    if (Tables.size() > static_cast<unsigned>(Info::MaxTables))

      condense();

    internal_key_type Key = Info::GetInternalKey(EKey);

    auto KeyHash = Info::ComputeHash(Key);

    if (MergedTable *M = getMergedTable()) {

      auto It = M->Data.find(Key);

      if (It != M->Data.end())

        Result = It->second;

    }

    data_type_builder ResultBuilder(Result);

    for (auto *ODT : tables()) {

      auto &HT = ODT->Table;

      auto It = HT.find_hashed(Key, KeyHash);

      if (It != HT.end())

        HT.getInfoObj().ReadDataInto(Key, It.getDataPtr(), It.getDataLen(),

                                     ResultBuilder);

    }

    return Result;

  }

  /// Read all the lookup results into a single value. This only makes

  /// sense if merging values across keys is meaningful.

  data_type findAll() {

    data_type Result;

    data_type_builder ResultBuilder(Result);

    if (!PendingOverrides.empty())

      removeOverriddenTables();

    if (MergedTable *M = getMergedTable()) {

      for (auto &KV : M->Data)

        Info::MergeDataInto(KV.second, ResultBuilder);

    }

    for (auto *ODT : tables()) {

      auto &HT = ODT->Table;

      Info &InfoObj = HT.getInfoObj();

      for (auto I = HT.data_begin(), E = HT.data_end(); I != E; 
++I326
) {

        auto *LocalPtr = I.getItem();

        // FIXME: Don't rely on the OnDiskHashTable format here.

        auto L = InfoObj.ReadKeyDataLength(LocalPtr);

        const internal_key_type &Key = InfoObj.ReadKey(LocalPtr, L.first);

        InfoObj.ReadDataInto(Key, LocalPtr + L.first, L.second, ResultBuilder);

      }

    }

    return Result;

  }

};

/// Writer for the on-disk hash table.

template<typename ReaderInfo, typename WriterInfo>

class MultiOnDiskHashTableGenerator {

  using BaseTable = MultiOnDiskHashTable<ReaderInfo>;

  using Generator = llvm::OnDiskChainedHashTableGenerator<WriterInfo>;

  Generator Gen;

public:

  MultiOnDiskHashTableGenerator() : Gen() {}

  void insert(typename WriterInfo::key_type_ref Key,

              typename WriterInfo::data_type_ref Data, WriterInfo &Info) {

    Gen.insert(Key, Data, Info);

  }

  void emit(llvm::SmallVectorImpl<char> &Out, WriterInfo &Info,

            const BaseTable *Base) {

    using namespace llvm::support;

    llvm::raw_svector_ostream OutStream(Out);

    // Write our header information.

    {

      endian::Writer Writer(OutStream, little);

      // Reserve four bytes for the bucket offset.

      Writer.write<uint32_t>(0);

      if (auto *Merged = Base ? Base->getMergedTable() : nullptr) {

        // Write list of overridden files.

        Writer.write<uint32_t>(Merged->Files.size());

        for (const auto &F : Merged->Files)

          Info.EmitFileRef(OutStream, F);

        // Add all merged entries from Base to the generator.

        for (auto &KV : Merged->Data) {

          if (!Gen.contains(KV.first, Info))

            Gen.insert(KV.first, Info.ImportData(KV.second), Info);

        }

      } else {

        Writer.write<uint32_t>(0);

      }

    }

    // Write the table itself.

    uint32_t BucketOffset = Gen.Emit(OutStream, Info);

    // Replace the first four bytes with the bucket offset.

    endian::write32le(Out.data(), BucketOffset);

  }

};

} // namespace serialization

} // namespace clang

#endif // LLVM_CLANG_LIB_SERIALIZATION_MULTIONDISKHASHTABLE_H