//===- SearchableTableEmitter.cpp - Generate efficiently searchable tables -==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This tablegen backend emits a generic array initialized by specified fields,
// together with companion index tables and lookup functions (binary search,
// currently).
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/MemoryBuffer.h"
#include "llvm/Support/SourceMgr.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"
#include <algorithm>
#include <string>
#include <vector>
using namespace llvm;

#define DEBUG_TYPE "searchable-table-emitter"

namespace {

class SearchableTableEmitter {
  RecordKeeper &Records;

public:
  SearchableTableEmitter(RecordKeeper &R) : Records(R) {}

  void run(raw_ostream &OS);

private:
  typedef std::pair<Init *, int> SearchTableEntry;

  int getAsInt(BitsInit *B) {
    return cast<IntInit>(B->convertInitializerTo(IntRecTy::get()))->getValue();
  }
  int getInt(Record *R, StringRef Field) {
    return getAsInt(R->getValueAsBitsInit(Field));
  }

  std::string primaryRepresentation(Init *I) {
    if (StringInit *SI = dyn_cast<StringInit>(I))
      return SI->getAsString();
    else if (BitsInit *BI = dyn_cast<BitsInit>(I))
      return "0x" + utohexstr(getAsInt(BI));
    else if (BitInit *BI = dyn_cast<BitInit>(I))
      return BI->getValue() ? "true" : "false";
    else if (CodeInit *CI = dyn_cast<CodeInit>(I)) {
      return CI->getValue();
    }
    PrintFatalError(SMLoc(),
                    "invalid field type, expected: string, bits, bit or code");
  }

  std::string searchRepresentation(Init *I) {
    std::string PrimaryRep = primaryRepresentation(I);
    if (!isa<StringInit>(I))
      return PrimaryRep;
    return StringRef(PrimaryRep).upper();
  }

  std::string searchableFieldType(Init *I) {
    if (isa<StringInit>(I))
      return "const char *";
    else if (BitsInit *BI = dyn_cast<BitsInit>(I)) {
      unsigned NumBits = BI->getNumBits();
      if (NumBits <= 8)
        NumBits = 8;
      else if (NumBits <= 16)
        NumBits = 16;
      else if (NumBits <= 32)
        NumBits = 32;
      else if (NumBits <= 64)
        NumBits = 64;
      else
        PrintFatalError(SMLoc(), "bitfield too large to search");
      return "uint" + utostr(NumBits) + "_t";
    }
    PrintFatalError(SMLoc(), "Unknown type to search by");
  }

  void emitMapping(Record *MappingDesc, raw_ostream &OS);
  void emitMappingEnum(std::vector<Record *> &Items, Record *InstanceClass,
                       raw_ostream &OS);
  void
  emitPrimaryTable(StringRef Name, std::vector<std::string> &FieldNames,
                   std::vector<std::string> &SearchFieldNames,
                   std::vector<std::vector<SearchTableEntry>> &SearchTables,
                   std::vector<Record *> &Items, raw_ostream &OS);
  void emitSearchTable(StringRef Name, StringRef Field,
                       std::vector<SearchTableEntry> &SearchTable,
                       raw_ostream &OS);
  void emitLookupDeclaration(StringRef Name, StringRef Field, Init *I,
                             raw_ostream &OS);
  void emitLookupFunction(StringRef Name, StringRef Field, Init *I,
                          raw_ostream &OS);
};

} // End anonymous namespace.

/// Emit an enum providing symbolic access to some preferred field from
/// C++.
void SearchableTableEmitter::emitMappingEnum(std::vector<Record *> &Items,
                                             Record *InstanceClass,
                                             raw_ostream &OS) {
  StringRef EnumNameField = InstanceClass->getValueAsString("EnumNameField");
  StringRef EnumValueField;
  if (!InstanceClass->isValueUnset("EnumValueField"))
    EnumValueField = InstanceClass->getValueAsString("EnumValueField");

  OS << "enum " << InstanceClass->getName() << "Values {\n";
  for (auto Item : Items) {
    OS << "  " << Item->getValueAsString(EnumNameField);
    if (EnumValueField != StringRef())
      OS << " = " << getInt(Item, EnumValueField);
    OS << ",\n";
  }
  OS << "};\n\n";
}

void SearchableTableEmitter::emitPrimaryTable(
    StringRef Name, std::vector<std::string> &FieldNames,
    std::vector<std::string> &SearchFieldNames,
    std::vector<std::vector<SearchTableEntry>> &SearchTables,
    std::vector<Record *> &Items, raw_ostream &OS) {
  OS << "const " << Name << " " << Name << "sList[] = {\n";

  for (auto Item : Items) {
    OS << "  { ";
    for (unsigned i = 0; i < FieldNames.size(); ++i) {
      OS << primaryRepresentation(Item->getValueInit(FieldNames[i]));
      if (i != FieldNames.size() - 1)
        OS << ", ";
    }
    OS << "},\n";
  }
  OS << "};\n\n";
}

void SearchableTableEmitter::emitSearchTable(
    StringRef Name, StringRef Field, std::vector<SearchTableEntry> &SearchTable,
    raw_ostream &OS) {
  OS << "const std::pair<" << searchableFieldType(SearchTable[0].first)
     << ", int> " << Name << "sBy" << Field << "[] = {\n";

  if (isa<BitsInit>(SearchTable[0].first)) {
    std::stable_sort(SearchTable.begin(), SearchTable.end(),
                     [this](const SearchTableEntry &LHS,
                            const SearchTableEntry &RHS) {
                       return getAsInt(cast<BitsInit>(LHS.first)) <
                              getAsInt(cast<BitsInit>(RHS.first));
                     });
  } else {
    std::stable_sort(SearchTable.begin(), SearchTable.end(),
                     [this](const SearchTableEntry &LHS,
                            const SearchTableEntry &RHS) {
                       return searchRepresentation(LHS.first) <
                              searchRepresentation(RHS.first);
                     });
  }

  for (auto Entry : SearchTable) {
    OS << "  { " << searchRepresentation(Entry.first) << ", " << Entry.second
       << " },\n";
  }
  OS << "};\n\n";
}

void SearchableTableEmitter::emitLookupFunction(StringRef Name, StringRef Field,
                                                Init *I, raw_ostream &OS) {
  bool IsIntegral = isa<BitsInit>(I);
  std::string FieldType = searchableFieldType(I);
  std::string PairType = "std::pair<" + FieldType + ", int>";

  // const SysRegs *lookupSysRegByName(const char *Name) {
  OS << "const " << Name << " *"
     << "lookup" << Name << "By" << Field;
  OS << "(" << (IsIntegral ? FieldType : "StringRef") << " " << Field
     << ") {\n";

  if (IsIntegral) {
    OS << "  auto CanonicalVal = " << Field << ";\n";
    OS << " " << PairType << " Val = {CanonicalVal, 0};\n";
  } else {
    // Make sure the result is null terminated because it's going via "char *".
    OS << "  std::string CanonicalVal = " << Field << ".upper();\n";
    OS << "  " << PairType << " Val = {CanonicalVal.c_str(), 0};\n";
  }

  OS << "  ArrayRef<" << PairType << "> Table(" << Name << "sBy" << Field
     << ");\n";
  OS << "  auto Idx = std::lower_bound(Table.begin(), Table.end(), Val";

  if (IsIntegral)
    OS << ");\n";
  else {
    OS << ",\n                              ";
    OS << "[](const " << PairType << " &LHS, const " << PairType
       << " &RHS) {\n";
    OS << "    return std::strcmp(LHS.first, RHS.first) < 0;\n";
    OS << "  });\n\n";
  }

  OS << "  if (Idx == Table.end() || CanonicalVal != Idx->first)\n";
  OS << "    return nullptr;\n";

  OS << "  return &" << Name << "sList[Idx->second];\n";
  OS << "}\n\n";
}

void SearchableTableEmitter::emitLookupDeclaration(StringRef Name,
                                                   StringRef Field, Init *I,
                                                   raw_ostream &OS) {
  bool IsIntegral = isa<BitsInit>(I);
  std::string FieldType = searchableFieldType(I);
  OS << "const " << Name << " *"
     << "lookup" << Name << "By" << Field;
  OS << "(" << (IsIntegral ? FieldType : "StringRef") << " " << Field
     << ");\n\n";
}

void SearchableTableEmitter::emitMapping(Record *InstanceClass,
                                         raw_ostream &OS) {
  StringRef TableName = InstanceClass->getName();
  std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);

  // Gather all the records we're going to need for this particular mapping.
  std::vector<std::vector<SearchTableEntry>> SearchTables;
  std::vector<std::string> SearchFieldNames;

  std::vector<std::string> FieldNames;
  for (const RecordVal &Field : InstanceClass->getValues()) {
    std::string FieldName = Field.getName();

    // Skip uninteresting fields: either built-in, special to us, or injected
    // template parameters (if they contain a ':').
    if (FieldName.find(':') != std::string::npos || FieldName == "NAME" ||
        FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
        FieldName == "EnumValueField")
      continue;

    FieldNames.push_back(FieldName);
  }

  for (auto *Field : *InstanceClass->getValueAsListInit("SearchableFields")) {
    SearchTables.emplace_back();
    SearchFieldNames.push_back(Field->getAsUnquotedString());
  }

  int Idx = 0;
  for (Record *Item : Items) {
    for (unsigned i = 0; i < SearchFieldNames.size(); ++i) {
      Init *SearchVal = Item->getValueInit(SearchFieldNames[i]);
      SearchTables[i].emplace_back(SearchVal, Idx);
    }
    ++Idx;
  }

  OS << "#ifdef GET_" << TableName.upper() << "_DECL\n";
  OS << "#undef GET_" << TableName.upper() << "_DECL\n";

  // Next emit the enum containing the top-level names for use in C++ code if
  // requested
  if (!InstanceClass->isValueUnset("EnumNameField")) {
    emitMappingEnum(Items, InstanceClass, OS);
  }

  // And the declarations for the functions that will perform lookup.
  for (unsigned i = 0; i < SearchFieldNames.size(); ++i)
    emitLookupDeclaration(TableName, SearchFieldNames[i],
                          SearchTables[i][0].first, OS);

  OS << "#endif\n\n";

  OS << "#ifdef GET_" << TableName.upper() << "_IMPL\n";
  OS << "#undef GET_" << TableName.upper() << "_IMPL\n";

  // The primary data table contains all the fields defined for this map.
  emitPrimaryTable(TableName, FieldNames, SearchFieldNames, SearchTables, Items,
                   OS);

  // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary
  // search can be performed by "Thing".
  for (unsigned i = 0; i < SearchTables.size(); ++i) {
    emitSearchTable(TableName, SearchFieldNames[i], SearchTables[i], OS);
    emitLookupFunction(TableName, SearchFieldNames[i], SearchTables[i][0].first,
                       OS);
  }

  OS << "#endif\n";
}

void SearchableTableEmitter::run(raw_ostream &OS) {
  // Tables are defined to be the direct descendents of "SearchableEntry".
  Record *SearchableTable = Records.getClass("SearchableTable");
  for (auto &NameRec : Records.getClasses()) {
    Record *Class = NameRec.second.get();
    if (Class->getSuperClasses().size() != 1 ||
        !Class->isSubClassOf(SearchableTable))
      continue;
    emitMapping(Class, OS);
  }
}

namespace llvm {

void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
  SearchableTableEmitter(RK).run(OS);
}

} // End llvm namespace.