//===----- MachOLinkGraphBuilder.h - MachO LinkGraph builder ----*- 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
//
//===----------------------------------------------------------------------===//
//
// Generic MachO LinkGraph building code.
//
//===----------------------------------------------------------------------===//

#ifndef LIB_EXECUTIONENGINE_JITLINK_MACHOLINKGRAPHBUILDER_H
#define LIB_EXECUTIONENGINE_JITLINK_MACHOLINKGRAPHBUILDER_H

#include "llvm/ExecutionEngine/JITLink/JITLink.h"

#include "EHFrameSupportImpl.h"
#include "JITLinkGeneric.h"
#include "llvm/Object/MachO.h"

#include <list>

namespace llvm {
namespace jitlink {

class MachOLinkGraphBuilder {
public:
  virtual ~MachOLinkGraphBuilder();
  Expected<std::unique_ptr<LinkGraph>> buildGraph();

protected:
  class MachOEHFrameBinaryParser : public EHFrameBinaryParser {
  public:
    MachOEHFrameBinaryParser(MachOLinkGraphBuilder &Builder,
                             JITTargetAddress EHFrameAddress,
                             StringRef EHFrameContent, Section &EHFrameSection,
                             uint64_t CIEAlignment, uint64_t FDEAlignment,
                             Edge::Kind FDEToCIERelocKind,
                             Edge::Kind FDEToTargetRelocKind)
        : EHFrameBinaryParser(EHFrameAddress, EHFrameContent,
                              Builder.getGraph().getPointerSize(),
                              Builder.getGraph().getEndianness()),
          Builder(Builder), EHFrameSection(EHFrameSection),
          CIEAlignment(CIEAlignment), FDEAlignment(FDEAlignment),
          FDEToCIERelocKind(FDEToCIERelocKind),
          FDEToTargetRelocKind(FDEToTargetRelocKind) {}

    Symbol *getSymbolAtAddress(JITTargetAddress Address) override {
      if (auto *Sym = Builder.getSymbolByAddress(Address))
        if (Sym->getAddress() == Address)
          return Sym;
      return nullptr;
    }

    Symbol &createCIERecord(JITTargetAddress RecordAddr,
                            StringRef RecordContent) override {
      auto &G = Builder.getGraph();
      auto &B = G.createContentBlock(EHFrameSection, RecordContent, RecordAddr,
                                     CIEAlignment, 0);
      auto &CIESymbol =
          G.addAnonymousSymbol(B, 0, RecordContent.size(), false, false);
      Builder.setCanonicalSymbol(CIESymbol);
      return CIESymbol;
    }

    Expected<Symbol &> createFDERecord(JITTargetAddress RecordAddr,
                                       StringRef RecordContent, Symbol &CIE,
                                       size_t CIEOffset, Symbol &Func,
                                       size_t FuncOffset, Symbol *LSDA,
                                       size_t LSDAOffset) override {
      auto &G = Builder.getGraph();
      auto &B = G.createContentBlock(EHFrameSection, RecordContent, RecordAddr,
                                     FDEAlignment, 0);

      // Add edges to CIE, Func, and (conditionally) LSDA.
      B.addEdge(FDEToCIERelocKind, CIEOffset, CIE, 0);
      B.addEdge(FDEToTargetRelocKind, FuncOffset, Func, 0);

      if (LSDA)
        B.addEdge(FDEToTargetRelocKind, LSDAOffset, *LSDA, 0);

      auto &FDESymbol =
          G.addAnonymousSymbol(B, 0, RecordContent.size(), false, false);

      // Add a keep-alive relocation from the function to the FDE to ensure it
      // is not dead stripped.
      Func.getBlock().addEdge(Edge::KeepAlive, 0, FDESymbol, 0);

      return FDESymbol;
    }

  private:
    MachOLinkGraphBuilder &Builder;
    Section &EHFrameSection;
    uint64_t CIEAlignment;
    uint64_t FDEAlignment;
    Edge::Kind FDEToCIERelocKind;
    Edge::Kind FDEToTargetRelocKind;
  };

  struct NormalizedSymbol {
    friend class MachOLinkGraphBuilder;

  private:
    NormalizedSymbol(Optional<StringRef> Name, uint64_t Value, uint8_t Type,
                     uint8_t Sect, uint16_t Desc, Linkage L, Scope S)
        : Name(Name), Value(Value), Type(Type), Sect(Sect), Desc(Desc), L(L),
          S(S) {
      assert((!Name || !Name->empty()) && "Name must be none or non-empty");
    }

  public:
    NormalizedSymbol(const NormalizedSymbol &) = delete;
    NormalizedSymbol &operator=(const NormalizedSymbol &) = delete;
    NormalizedSymbol(NormalizedSymbol &&) = delete;
    NormalizedSymbol &operator=(NormalizedSymbol &&) = delete;

    Optional<StringRef> Name;
    uint64_t Value = 0;
    uint8_t Type = 0;
    uint8_t Sect = 0;
    uint16_t Desc = 0;
    Linkage L = Linkage::Strong;
    Scope S = Scope::Default;
    Symbol *GraphSymbol = nullptr;
  };

  class NormalizedSection {
    friend class MachOLinkGraphBuilder;

  private:
    NormalizedSection() = default;

  public:
    Section *GraphSection = nullptr;
    uint64_t Address = 0;
    uint64_t Size = 0;
    uint64_t Alignment = 0;
    uint32_t Flags = 0;
    const char *Data = nullptr;
  };

  using SectionParserFunction = std::function<Error(NormalizedSection &S)>;

  MachOLinkGraphBuilder(const object::MachOObjectFile &Obj);

  LinkGraph &getGraph() const { return *G; }

  const object::MachOObjectFile &getObject() const { return Obj; }

  void addCustomSectionParser(StringRef SectionName,
                              SectionParserFunction Parse);

  virtual Error addRelocations() = 0;

  /// Create a symbol.
  template <typename... ArgTs>
  NormalizedSymbol &createNormalizedSymbol(ArgTs &&... Args) {
    NormalizedSymbol *Sym = reinterpret_cast<NormalizedSymbol *>(
        Allocator.Allocate<NormalizedSymbol>());
    new (Sym) NormalizedSymbol(std::forward<ArgTs>(Args)...);
    return *Sym;
  }

  /// Index is zero-based (MachO section indexes are usually one-based) and
  /// assumed to be in-range. Client is responsible for checking.
  NormalizedSection &getSectionByIndex(unsigned Index) {
    auto I = IndexToSection.find(Index);
    assert(I != IndexToSection.end() && "No section recorded at index");
    return I->second;
  }

  /// Try to get the section at the given index. Will return an error if the
  /// given index is out of range, or if no section has been added for the given
  /// index.
  Expected<NormalizedSection &> findSectionByIndex(unsigned Index) {
    auto I = IndexToSection.find(Index);
    if (I == IndexToSection.end())
      return make_error<JITLinkError>("No section recorded for index " +
                                      formatv("{0:u}", Index));
    return I->second;
  }

  /// Try to get the symbol at the given index. Will return an error if the
  /// given index is out of range, or if no symbol has been added for the given
  /// index.
  Expected<NormalizedSymbol &> findSymbolByIndex(uint64_t Index) {
    if (Index >= IndexToSymbol.size())
      return make_error<JITLinkError>("Symbol index out of range");
    auto *Sym = IndexToSymbol[Index];
    if (!Sym)
      return make_error<JITLinkError>("No symbol at index " +
                                      formatv("{0:u}", Index));
    return *Sym;
  }

  /// Returns the symbol with the highest address not greater than the search
  /// address, or null if no such symbol exists.
  Symbol *getSymbolByAddress(JITTargetAddress Address) {
    auto I = AddrToCanonicalSymbol.upper_bound(Address);
    if (I == AddrToCanonicalSymbol.begin())
      return nullptr;
    return std::prev(I)->second;
  }

  /// Returns the symbol with the highest address not greater than the search
  /// address, or an error if no such symbol exists.
  Expected<Symbol &> findSymbolByAddress(JITTargetAddress Address) {
    auto *Sym = getSymbolByAddress(Address);
    if (Sym)
      if (Address < Sym->getAddress() + Sym->getSize())
        return *Sym;
    return make_error<JITLinkError>("No symbol covering address " +
                                    formatv("{0:x16}", Address));
  }

  static Linkage getLinkage(uint16_t Desc);
  static Scope getScope(StringRef Name, uint8_t Type);
  static bool isAltEntry(const NormalizedSymbol &NSym);

private:
  static unsigned getPointerSize(const object::MachOObjectFile &Obj);
  static support::endianness getEndianness(const object::MachOObjectFile &Obj);

  void setCanonicalSymbol(Symbol &Sym) {
    auto *&CanonicalSymEntry = AddrToCanonicalSymbol[Sym.getAddress()];
    // There should be no symbol at this address, or, if there is,
    // it should be a zero-sized symbol from an empty section (which
    // we can safely override).
    assert((!CanonicalSymEntry || CanonicalSymEntry->getSize() == 0) &&
           "Duplicate canonical symbol at address");
    CanonicalSymEntry = &Sym;
  }

  Section &getCommonSection();
  void addSectionStartSymAndBlock(Section &GraphSec, uint64_t Address,
                                  const char *Data, uint64_t Size,
                                  uint32_t Alignment, bool IsLive);

  Error createNormalizedSections();
  Error createNormalizedSymbols();

  /// Create graph blocks and symbols for externals, absolutes, commons and
  /// all defined symbols in sections without custom parsers.
  Error graphifyRegularSymbols();

  /// Create graph blocks and symbols for all sections.
  Error graphifySectionsWithCustomParsers();

  // Put the BumpPtrAllocator first so that we don't free any of the underlying
  // memory until the Symbol/Addressable destructors have been run.
  BumpPtrAllocator Allocator;

  const object::MachOObjectFile &Obj;
  std::unique_ptr<LinkGraph> G;

  DenseMap<unsigned, NormalizedSection> IndexToSection;
  Section *CommonSection = nullptr;

  DenseMap<uint32_t, NormalizedSymbol *> IndexToSymbol;
  std::map<JITTargetAddress, Symbol *> AddrToCanonicalSymbol;
  StringMap<SectionParserFunction> CustomSectionParserFunctions;
};

} // end namespace jitlink
} // end namespace llvm

#endif // LIB_EXECUTIONENGINE_JITLINK_MACHOLINKGRAPHBUILDER_H