1//===- SearchableTableEmitter.cpp - Generate efficiently searchable tables -==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This tablegen backend emits a generic array initialized by specified fields,
10// together with companion index tables and lookup functions (binary search,
11// currently).
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/StringExtras.h"
17#include "llvm/Support/Format.h"
18#include "llvm/Support/MemoryBuffer.h"
19#include "llvm/Support/SourceMgr.h"
20#include "llvm/TableGen/Error.h"
21#include "llvm/TableGen/Record.h"
22#include "CodeGenIntrinsics.h"
23#include <algorithm>
24#include <set>
25#include <string>
26#include <vector>
27
28using namespace llvm;
29
30#define DEBUG_TYPE "searchable-table-emitter"
31
32namespace {
33
34struct GenericTable;
35
36int getAsInt(Init *B) {
37  return cast<IntInit>(B->convertInitializerTo(IntRecTy::get()))->getValue();
38}
39int getInt(Record *R, StringRef Field) {
40  return getAsInt(R->getValueInit(Field));
41}
42
43struct GenericEnum {
44  using Entry = std::pair<StringRef, int64_t>;
45
46  std::string Name;
47  Record *Class = nullptr;
48  std::string PreprocessorGuard;
49  std::vector<std::unique_ptr<Entry>> Entries;
50  DenseMap<Record *, Entry *> EntryMap;
51};
52
53struct GenericField {
54  std::string Name;
55  RecTy *RecType = nullptr;
56  bool IsIntrinsic = false;
57  bool IsInstruction = false;
58  GenericEnum *Enum = nullptr;
59
60  GenericField(StringRef Name) : Name(Name) {}
61};
62
63struct SearchIndex {
64  std::string Name;
65  SmallVector<GenericField, 1> Fields;
66  bool EarlyOut = false;
67};
68
69struct GenericTable {
70  std::string Name;
71  std::string PreprocessorGuard;
72  std::string CppTypeName;
73  SmallVector<GenericField, 2> Fields;
74  std::vector<Record *> Entries;
75
76  std::unique_ptr<SearchIndex> PrimaryKey;
77  SmallVector<std::unique_ptr<SearchIndex>, 2> Indices;
78
79  const GenericField *getFieldByName(StringRef Name) const {
80    for (const auto &Field : Fields) {
81      if (Name == Field.Name)
82        return &Field;
83    }
84    return nullptr;
85  }
86};
87
88class SearchableTableEmitter {
89  RecordKeeper &Records;
90  DenseMap<Init *, std::unique_ptr<CodeGenIntrinsic>> Intrinsics;
91  std::vector<std::unique_ptr<GenericEnum>> Enums;
92  DenseMap<Record *, GenericEnum *> EnumMap;
93  std::set<std::string> PreprocessorGuards;
94
95public:
96  SearchableTableEmitter(RecordKeeper &R) : Records(R) {}
97
98  void run(raw_ostream &OS);
99
100private:
101  typedef std::pair<Init *, int> SearchTableEntry;
102
103  enum TypeContext {
104    TypeInStaticStruct,
105    TypeInTempStruct,
106    TypeInArgument,
107  };
108
109  std::string primaryRepresentation(const GenericField &Field, Init *I) {
110    if (StringInit *SI = dyn_cast<StringInit>(I))
111      return SI->getAsString();
112    else if (BitsInit *BI = dyn_cast<BitsInit>(I))
113      return "0x" + utohexstr(getAsInt(BI));
114    else if (BitInit *BI = dyn_cast<BitInit>(I))
115      return BI->getValue() ? "true" : "false";
116    else if (CodeInit *CI = dyn_cast<CodeInit>(I))
117      return CI->getValue();
118    else if (Field.IsIntrinsic)
119      return "Intrinsic::" + getIntrinsic(I).EnumName;
120    else if (Field.IsInstruction)
121      return I->getAsString();
122    else if (Field.Enum)
123      return Field.Enum->EntryMap[cast<DefInit>(I)->getDef()]->first;
124    PrintFatalError(Twine("invalid field type for field '") + Field.Name +
125                    "', expected: string, bits, bit or code");
126  }
127
128  bool isIntrinsic(Init *I) {
129    if (DefInit *DI = dyn_cast<DefInit>(I))
130      return DI->getDef()->isSubClassOf("Intrinsic");
131    return false;
132  }
133
134  CodeGenIntrinsic &getIntrinsic(Init *I) {
135    std::unique_ptr<CodeGenIntrinsic> &Intr = Intrinsics[I];
136    if (!Intr)
137      Intr = std::make_unique<CodeGenIntrinsic>(cast<DefInit>(I)->getDef());
138    return *Intr;
139  }
140
141  bool compareBy(Record *LHS, Record *RHS, const SearchIndex &Index);
142
143  bool isIntegral(Init *I) {
144    return isa<BitsInit>(I) || isa<CodeInit>(I) || isIntrinsic(I);
145  }
146
147  std::string searchableFieldType(const GenericField &Field, TypeContext Ctx) {
148    if (isa<StringRecTy>(Field.RecType)) {
149      if (Ctx == TypeInStaticStruct)
150        return "const char *";
151      if (Ctx == TypeInTempStruct)
152        return "std::string";
153      return "StringRef";
154    } else if (BitsRecTy *BI = dyn_cast<BitsRecTy>(Field.RecType)) {
155      unsigned NumBits = BI->getNumBits();
156      if (NumBits <= 8)
157        return "uint8_t";
158      if (NumBits <= 16)
159        return "uint16_t";
160      if (NumBits <= 32)
161        return "uint32_t";
162      if (NumBits <= 64)
163        return "uint64_t";
164      PrintFatalError(Twine("bitfield '") + Field.Name +
165                      "' too large to search");
166    } else if (Field.Enum || Field.IsIntrinsic || Field.IsInstruction)
167      return "unsigned";
168    PrintFatalError(Twine("Field '") + Field.Name + "' has unknown type '" +
169                    Field.RecType->getAsString() + "' to search by");
170  }
171
172  void emitGenericTable(const GenericTable &Table, raw_ostream &OS);
173  void emitGenericEnum(const GenericEnum &Enum, raw_ostream &OS);
174  void emitLookupDeclaration(const GenericTable &Table,
175                             const SearchIndex &Index, raw_ostream &OS);
176  void emitLookupFunction(const GenericTable &Table, const SearchIndex &Index,
177                          bool IsPrimary, raw_ostream &OS);
178  void emitIfdef(StringRef Guard, raw_ostream &OS);
179
180  bool parseFieldType(GenericField &Field, Init *II);
181  std::unique_ptr<SearchIndex>
182  parseSearchIndex(GenericTable &Table, StringRef Name,
183                   const std::vector<StringRef> &Key, bool EarlyOut);
184  void collectEnumEntries(GenericEnum &Enum, StringRef NameField,
185                          StringRef ValueField,
186                          const std::vector<Record *> &Items);
187  void collectTableEntries(GenericTable &Table,
188                           const std::vector<Record *> &Items);
189};
190
191} // End anonymous namespace.
192
193// For search indices that consists of a single field whose numeric value is
194// known, return that numeric value.
195static int64_t getNumericKey(const SearchIndex &Index, Record *Rec) {
196  assert(Index.Fields.size() == 1);
197
198  if (Index.Fields[0].Enum) {
199    Record *EnumEntry = Rec->getValueAsDef(Index.Fields[0].Name);
200    return Index.Fields[0].Enum->EntryMap[EnumEntry]->second;
201  }
202
203  return getInt(Rec, Index.Fields[0].Name);
204}
205
206/// Less-than style comparison between \p LHS and \p RHS according to the
207/// key of \p Index.
208bool SearchableTableEmitter::compareBy(Record *LHS, Record *RHS,
209                                       const SearchIndex &Index) {
210  for (const auto &Field : Index.Fields) {
211    Init *LHSI = LHS->getValueInit(Field.Name);
212    Init *RHSI = RHS->getValueInit(Field.Name);
213
214    if (isa<BitsRecTy>(Field.RecType) || isa<IntRecTy>(Field.RecType)) {
215      int64_t LHSi = getAsInt(LHSI);
216      int64_t RHSi = getAsInt(RHSI);
217      if (LHSi < RHSi)
218        return true;
219      if (LHSi > RHSi)
220        return false;
221    } else if (Field.IsIntrinsic) {
222      CodeGenIntrinsic &LHSi = getIntrinsic(LHSI);
223      CodeGenIntrinsic &RHSi = getIntrinsic(RHSI);
224      if (std::tie(LHSi.TargetPrefix, LHSi.Name) <
225          std::tie(RHSi.TargetPrefix, RHSi.Name))
226        return true;
227      if (std::tie(LHSi.TargetPrefix, LHSi.Name) >
228          std::tie(RHSi.TargetPrefix, RHSi.Name))
229        return false;
230    } else if (Field.IsInstruction) {
231      // This does not correctly compare the predefined instructions!
232      Record *LHSr = cast<DefInit>(LHSI)->getDef();
233      Record *RHSr = cast<DefInit>(RHSI)->getDef();
234
235      bool LHSpseudo = LHSr->getValueAsBit("isPseudo");
236      bool RHSpseudo = RHSr->getValueAsBit("isPseudo");
237      if (LHSpseudo && !RHSpseudo)
238        return true;
239      if (!LHSpseudo && RHSpseudo)
240        return false;
241
242      int comp = LHSr->getName().compare(RHSr->getName());
243      if (comp < 0)
244        return true;
245      if (comp > 0)
246        return false;
247    } else if (Field.Enum) {
248      auto LHSr = cast<DefInit>(LHSI)->getDef();
249      auto RHSr = cast<DefInit>(RHSI)->getDef();
250      int64_t LHSv = Field.Enum->EntryMap[LHSr]->second;
251      int64_t RHSv = Field.Enum->EntryMap[RHSr]->second;
252      if (LHSv < RHSv)
253        return true;
254      if (LHSv > RHSv)
255        return false;
256    } else {
257      std::string LHSs = primaryRepresentation(Field, LHSI);
258      std::string RHSs = primaryRepresentation(Field, RHSI);
259
260      if (isa<StringRecTy>(Field.RecType)) {
261        LHSs = StringRef(LHSs).upper();
262        RHSs = StringRef(RHSs).upper();
263      }
264
265      int comp = LHSs.compare(RHSs);
266      if (comp < 0)
267        return true;
268      if (comp > 0)
269        return false;
270    }
271  }
272  return false;
273}
274
275void SearchableTableEmitter::emitIfdef(StringRef Guard, raw_ostream &OS) {
276  OS << "#ifdef " << Guard << "\n";
277  PreprocessorGuards.insert(Guard);
278}
279
280/// Emit a generic enum.
281void SearchableTableEmitter::emitGenericEnum(const GenericEnum &Enum,
282                                             raw_ostream &OS) {
283  emitIfdef((Twine("GET_") + Enum.PreprocessorGuard + "_DECL").str(), OS);
284
285  OS << "enum " << Enum.Name << " {\n";
286  for (const auto &Entry : Enum.Entries)
287    OS << "  " << Entry->first << " = " << Entry->second << ",\n";
288  OS << "};\n";
289
290  OS << "#endif\n\n";
291}
292
293void SearchableTableEmitter::emitLookupFunction(const GenericTable &Table,
294                                                const SearchIndex &Index,
295                                                bool IsPrimary,
296                                                raw_ostream &OS) {
297  OS << "\n";
298  emitLookupDeclaration(Table, Index, OS);
299  OS << " {\n";
300
301  std::vector<Record *> IndexRowsStorage;
302  ArrayRef<Record *> IndexRows;
303  StringRef IndexTypeName;
304  StringRef IndexName;
305
306  if (IsPrimary) {
307    IndexTypeName = Table.CppTypeName;
308    IndexName = Table.Name;
309    IndexRows = Table.Entries;
310  } else {
311    OS << "  struct IndexType {\n";
312    for (const auto &Field : Index.Fields) {
313      OS << "    " << searchableFieldType(Field, TypeInStaticStruct) << " "
314         << Field.Name << ";\n";
315    }
316    OS << "    unsigned _index;\n";
317    OS << "  };\n";
318
319    OS << "  static const struct IndexType Index[] = {\n";
320
321    std::vector<std::pair<Record *, unsigned>> Entries;
322    Entries.reserve(Table.Entries.size());
323    for (unsigned i = 0; i < Table.Entries.size(); ++i)
324      Entries.emplace_back(Table.Entries[i], i);
325
326    std::stable_sort(Entries.begin(), Entries.end(),
327                     [&](const std::pair<Record *, unsigned> &LHS,
328                         const std::pair<Record *, unsigned> &RHS) {
329                       return compareBy(LHS.first, RHS.first, Index);
330                     });
331
332    IndexRowsStorage.reserve(Entries.size());
333    for (const auto &Entry : Entries) {
334      IndexRowsStorage.push_back(Entry.first);
335
336      OS << "    { ";
337      bool NeedComma = false;
338      for (const auto &Field : Index.Fields) {
339        if (NeedComma)
340          OS << ", ";
341        NeedComma = true;
342
343        std::string Repr =
344            primaryRepresentation(Field, Entry.first->getValueInit(Field.Name));
345        if (isa<StringRecTy>(Field.RecType))
346          Repr = StringRef(Repr).upper();
347        OS << Repr;
348      }
349      OS << ", " << Entry.second << " },\n";
350    }
351
352    OS << "  };\n\n";
353
354    IndexTypeName = "IndexType";
355    IndexName = "Index";
356    IndexRows = IndexRowsStorage;
357  }
358
359  bool IsContiguous = false;
360
361  if (Index.Fields.size() == 1 &&
362      (Index.Fields[0].Enum || isa<BitsRecTy>(Index.Fields[0].RecType))) {
363    IsContiguous = true;
364    for (unsigned i = 0; i < IndexRows.size(); ++i) {
365      if (getNumericKey(Index, IndexRows[i]) != i) {
366        IsContiguous = false;
367        break;
368      }
369    }
370  }
371
372  if (IsContiguous) {
373    OS << "  auto Table = makeArrayRef(" << IndexName << ");\n";
374    OS << "  size_t Idx = " << Index.Fields[0].Name << ";\n";
375    OS << "  return Idx >= Table.size() ? nullptr : ";
376    if (IsPrimary)
377      OS << "&Table[Idx]";
378    else
379      OS << "&" << Table.Name << "[Table[Idx]._index]";
380    OS << ";\n";
381    OS << "}\n";
382    return;
383  }
384
385  if (Index.EarlyOut) {
386    const GenericField &Field = Index.Fields[0];
387    std::string FirstRepr =
388        primaryRepresentation(Field, IndexRows[0]->getValueInit(Field.Name));
389    std::string LastRepr = primaryRepresentation(
390        Field, IndexRows.back()->getValueInit(Field.Name));
391    OS << "  if ((" << Field.Name << " < " << FirstRepr << ") ||\n";
392    OS << "      (" << Field.Name << " > " << LastRepr << "))\n";
393    OS << "    return nullptr;\n\n";
394  }
395
396  OS << "  struct KeyType {\n";
397  for (const auto &Field : Index.Fields) {
398    OS << "    " << searchableFieldType(Field, TypeInTempStruct) << " "
399       << Field.Name << ";\n";
400  }
401  OS << "  };\n";
402  OS << "  KeyType Key = { ";
403  bool NeedComma = false;
404  for (const auto &Field : Index.Fields) {
405    if (NeedComma)
406      OS << ", ";
407    NeedComma = true;
408
409    OS << Field.Name;
410    if (isa<StringRecTy>(Field.RecType)) {
411      OS << ".upper()";
412      if (IsPrimary)
413        PrintFatalError(Twine("Use a secondary index for case-insensitive "
414                              "comparison of field '") +
415                        Field.Name + "' in table '" + Table.Name + "'");
416    }
417  }
418  OS << " };\n";
419
420  OS << "  auto Table = makeArrayRef(" << IndexName << ");\n";
421  OS << "  auto Idx = std::lower_bound(Table.begin(), Table.end(), Key,\n";
422  OS << "    [](const " << IndexTypeName << " &LHS, const KeyType &RHS) {\n";
423
424  for (const auto &Field : Index.Fields) {
425    if (isa<StringRecTy>(Field.RecType)) {
426      OS << "      int Cmp" << Field.Name << " = StringRef(LHS." << Field.Name
427         << ").compare(RHS." << Field.Name << ");\n";
428      OS << "      if (Cmp" << Field.Name << " < 0) return true;\n";
429      OS << "      if (Cmp" << Field.Name << " > 0) return false;\n";
430    } else if (Field.Enum) {
431      // Explicitly cast to unsigned, because the signedness of enums is
432      // compiler-dependent.
433      OS << "      if ((unsigned)LHS." << Field.Name << " < (unsigned)RHS."
434         << Field.Name << ")\n";
435      OS << "        return true;\n";
436      OS << "      if ((unsigned)LHS." << Field.Name << " > (unsigned)RHS."
437         << Field.Name << ")\n";
438      OS << "        return false;\n";
439    } else {
440      OS << "      if (LHS." << Field.Name << " < RHS." << Field.Name << ")\n";
441      OS << "        return true;\n";
442      OS << "      if (LHS." << Field.Name << " > RHS." << Field.Name << ")\n";
443      OS << "        return false;\n";
444    }
445  }
446
447  OS << "      return false;\n";
448  OS << "    });\n\n";
449
450  OS << "  if (Idx == Table.end()";
451
452  for (const auto &Field : Index.Fields)
453    OS << " ||\n      Key." << Field.Name << " != Idx->" << Field.Name;
454  OS << ")\n    return nullptr;\n";
455
456  if (IsPrimary)
457    OS << "  return &*Idx;\n";
458  else
459    OS << "  return &" << Table.Name << "[Idx->_index];\n";
460
461  OS << "}\n";
462}
463
464void SearchableTableEmitter::emitLookupDeclaration(const GenericTable &Table,
465                                                   const SearchIndex &Index,
466                                                   raw_ostream &OS) {
467  OS << "const " << Table.CppTypeName << " *" << Index.Name << "(";
468
469  bool NeedComma = false;
470  for (const auto &Field : Index.Fields) {
471    if (NeedComma)
472      OS << ", ";
473    NeedComma = true;
474
475    OS << searchableFieldType(Field, TypeInArgument) << " " << Field.Name;
476  }
477  OS << ")";
478}
479
480void SearchableTableEmitter::emitGenericTable(const GenericTable &Table,
481                                              raw_ostream &OS) {
482  emitIfdef((Twine("GET_") + Table.PreprocessorGuard + "_DECL").str(), OS);
483
484  // Emit the declarations for the functions that will perform lookup.
485  if (Table.PrimaryKey) {
486    emitLookupDeclaration(Table, *Table.PrimaryKey, OS);
487    OS << ";\n";
488  }
489  for (const auto &Index : Table.Indices) {
490    emitLookupDeclaration(Table, *Index, OS);
491    OS << ";\n";
492  }
493
494  OS << "#endif\n\n";
495
496  emitIfdef((Twine("GET_") + Table.PreprocessorGuard + "_IMPL").str(), OS);
497
498  // The primary data table contains all the fields defined for this map.
499  OS << "constexpr " << Table.CppTypeName << " " << Table.Name << "[] = {\n";
500  for (unsigned i = 0; i < Table.Entries.size(); ++i) {
501    Record *Entry = Table.Entries[i];
502    OS << "  { ";
503
504    bool NeedComma = false;
505    for (const auto &Field : Table.Fields) {
506      if (NeedComma)
507        OS << ", ";
508      NeedComma = true;
509
510      OS << primaryRepresentation(Field, Entry->getValueInit(Field.Name));
511    }
512
513    OS << " }, // " << i << "\n";
514  }
515  OS << " };\n";
516
517  // Indexes are sorted "{ Thing, PrimaryIdx }" arrays, so that a binary
518  // search can be performed by "Thing".
519  if (Table.PrimaryKey)
520    emitLookupFunction(Table, *Table.PrimaryKey, true, OS);
521  for (const auto &Index : Table.Indices)
522    emitLookupFunction(Table, *Index, false, OS);
523
524  OS << "#endif\n\n";
525}
526
527bool SearchableTableEmitter::parseFieldType(GenericField &Field, Init *II) {
528  if (auto DI = dyn_cast<DefInit>(II)) {
529    Record *TypeRec = DI->getDef();
530    if (TypeRec->isSubClassOf("GenericEnum")) {
531      Field.Enum = EnumMap[TypeRec];
532      Field.RecType = RecordRecTy::get(Field.Enum->Class);
533      return true;
534    }
535  }
536
537  return false;
538}
539
540std::unique_ptr<SearchIndex>
541SearchableTableEmitter::parseSearchIndex(GenericTable &Table, StringRef Name,
542                                         const std::vector<StringRef> &Key,
543                                         bool EarlyOut) {
544  auto Index = std::make_unique<SearchIndex>();
545  Index->Name = Name;
546  Index->EarlyOut = EarlyOut;
547
548  for (const auto &FieldName : Key) {
549    const GenericField *Field = Table.getFieldByName(FieldName);
550    if (!Field)
551      PrintFatalError(Twine("Search index '") + Name +
552                      "' refers to non-existing field '" + FieldName +
553                      "' in table '" + Table.Name + "'");
554    Index->Fields.push_back(*Field);
555  }
556
557  if (EarlyOut && isa<StringRecTy>(Index->Fields[0].RecType)) {
558    PrintFatalError(
559        "Early-out is not supported for string types (in search index '" +
560        Twine(Name) + "'");
561  }
562
563  return Index;
564}
565
566void SearchableTableEmitter::collectEnumEntries(
567    GenericEnum &Enum, StringRef NameField, StringRef ValueField,
568    const std::vector<Record *> &Items) {
569  for (auto EntryRec : Items) {
570    StringRef Name;
571    if (NameField.empty())
572      Name = EntryRec->getName();
573    else
574      Name = EntryRec->getValueAsString(NameField);
575
576    int64_t Value = 0;
577    if (!ValueField.empty())
578      Value = getInt(EntryRec, ValueField);
579
580    Enum.Entries.push_back(std::make_unique<GenericEnum::Entry>(Name, Value));
581    Enum.EntryMap.insert(std::make_pair(EntryRec, Enum.Entries.back().get()));
582  }
583
584  if (ValueField.empty()) {
585    std::stable_sort(Enum.Entries.begin(), Enum.Entries.end(),
586                     [](const std::unique_ptr<GenericEnum::Entry> &LHS,
587                        const std::unique_ptr<GenericEnum::Entry> &RHS) {
588                       return LHS->first < RHS->first;
589                     });
590
591    for (size_t i = 0; i < Enum.Entries.size(); ++i)
592      Enum.Entries[i]->second = i;
593  }
594}
595
596void SearchableTableEmitter::collectTableEntries(
597    GenericTable &Table, const std::vector<Record *> &Items) {
598  for (auto EntryRec : Items) {
599    for (auto &Field : Table.Fields) {
600      auto TI = dyn_cast<TypedInit>(EntryRec->getValueInit(Field.Name));
601      if (!TI) {
602        PrintFatalError(EntryRec->getLoc(),
603                        Twine("Record '") + EntryRec->getName() +
604                            "' in table '" + Table.Name +
605                            "' is missing field '" + Field.Name + "'");
606      }
607      if (!Field.RecType) {
608        Field.RecType = TI->getType();
609      } else {
610        RecTy *Ty = resolveTypes(Field.RecType, TI->getType());
611        if (!Ty)
612          PrintFatalError(Twine("Field '") + Field.Name + "' of table '" +
613                          Table.Name + "' has incompatible type: " +
614                          Field.RecType->getAsString() + " vs. " +
615                          TI->getType()->getAsString());
616        Field.RecType = Ty;
617      }
618    }
619
620    Table.Entries.push_back(EntryRec);
621  }
622
623  Record *IntrinsicClass = Records.getClass("Intrinsic");
624  Record *InstructionClass = Records.getClass("Instruction");
625  for (auto &Field : Table.Fields) {
626    if (auto RecordTy = dyn_cast<RecordRecTy>(Field.RecType)) {
627      if (IntrinsicClass && RecordTy->isSubClassOf(IntrinsicClass))
628        Field.IsIntrinsic = true;
629      else if (InstructionClass && RecordTy->isSubClassOf(InstructionClass))
630        Field.IsInstruction = true;
631    }
632  }
633}
634
635void SearchableTableEmitter::run(raw_ostream &OS) {
636  // Emit tables in a deterministic order to avoid needless rebuilds.
637  SmallVector<std::unique_ptr<GenericTable>, 4> Tables;
638  DenseMap<Record *, GenericTable *> TableMap;
639
640  // Collect all definitions first.
641  for (auto EnumRec : Records.getAllDerivedDefinitions("GenericEnum")) {
642    StringRef NameField;
643    if (!EnumRec->isValueUnset("NameField"))
644      NameField = EnumRec->getValueAsString("NameField");
645
646    StringRef ValueField;
647    if (!EnumRec->isValueUnset("ValueField"))
648      ValueField = EnumRec->getValueAsString("ValueField");
649
650    auto Enum = std::make_unique<GenericEnum>();
651    Enum->Name = EnumRec->getName();
652    Enum->PreprocessorGuard = EnumRec->getName();
653
654    StringRef FilterClass = EnumRec->getValueAsString("FilterClass");
655    Enum->Class = Records.getClass(FilterClass);
656    if (!Enum->Class)
657      PrintFatalError(EnumRec->getLoc(), Twine("Enum FilterClass '") +
658                                             FilterClass + "' does not exist");
659
660    collectEnumEntries(*Enum, NameField, ValueField,
661                       Records.getAllDerivedDefinitions(FilterClass));
662    EnumMap.insert(std::make_pair(EnumRec, Enum.get()));
663    Enums.emplace_back(std::move(Enum));
664  }
665
666  for (auto TableRec : Records.getAllDerivedDefinitions("GenericTable")) {
667    auto Table = std::make_unique<GenericTable>();
668    Table->Name = TableRec->getName();
669    Table->PreprocessorGuard = TableRec->getName();
670    Table->CppTypeName = TableRec->getValueAsString("CppTypeName");
671
672    std::vector<StringRef> Fields = TableRec->getValueAsListOfStrings("Fields");
673    for (const auto &FieldName : Fields) {
674      Table->Fields.emplace_back(FieldName);
675
676      if (auto TypeOfVal = TableRec->getValue(("TypeOf_" + FieldName).str())) {
677        if (!parseFieldType(Table->Fields.back(), TypeOfVal->getValue())) {
678          PrintFatalError(TableRec->getLoc(),
679                          Twine("Table '") + Table->Name +
680                              "' has bad 'TypeOf_" + FieldName +
681                              "': " + TypeOfVal->getValue()->getAsString());
682        }
683      }
684    }
685
686    collectTableEntries(*Table, Records.getAllDerivedDefinitions(
687                                    TableRec->getValueAsString("FilterClass")));
688
689    if (!TableRec->isValueUnset("PrimaryKey")) {
690      Table->PrimaryKey =
691          parseSearchIndex(*Table, TableRec->getValueAsString("PrimaryKeyName"),
692                           TableRec->getValueAsListOfStrings("PrimaryKey"),
693                           TableRec->getValueAsBit("PrimaryKeyEarlyOut"));
694
695      std::stable_sort(Table->Entries.begin(), Table->Entries.end(),
696                       [&](Record *LHS, Record *RHS) {
697                         return compareBy(LHS, RHS, *Table->PrimaryKey);
698                       });
699    }
700
701    TableMap.insert(std::make_pair(TableRec, Table.get()));
702    Tables.emplace_back(std::move(Table));
703  }
704
705  for (Record *IndexRec : Records.getAllDerivedDefinitions("SearchIndex")) {
706    Record *TableRec = IndexRec->getValueAsDef("Table");
707    auto It = TableMap.find(TableRec);
708    if (It == TableMap.end())
709      PrintFatalError(IndexRec->getLoc(),
710                      Twine("SearchIndex '") + IndexRec->getName() +
711                          "' refers to non-existing table '" +
712                          TableRec->getName());
713
714    GenericTable &Table = *It->second;
715    Table.Indices.push_back(parseSearchIndex(
716        Table, IndexRec->getName(), IndexRec->getValueAsListOfStrings("Key"),
717        IndexRec->getValueAsBit("EarlyOut")));
718  }
719
720  // Translate legacy tables.
721  Record *SearchableTable = Records.getClass("SearchableTable");
722  for (auto &NameRec : Records.getClasses()) {
723    Record *Class = NameRec.second.get();
724    if (Class->getSuperClasses().size() != 1 ||
725        !Class->isSubClassOf(SearchableTable))
726      continue;
727
728    StringRef TableName = Class->getName();
729    std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
730    if (!Class->isValueUnset("EnumNameField")) {
731      StringRef NameField = Class->getValueAsString("EnumNameField");
732      StringRef ValueField;
733      if (!Class->isValueUnset("EnumValueField"))
734        ValueField = Class->getValueAsString("EnumValueField");
735
736      auto Enum = std::make_unique<GenericEnum>();
737      Enum->Name = (Twine(Class->getName()) + "Values").str();
738      Enum->PreprocessorGuard = Class->getName().upper();
739      Enum->Class = Class;
740
741      collectEnumEntries(*Enum, NameField, ValueField, Items);
742
743      Enums.emplace_back(std::move(Enum));
744    }
745
746    auto Table = std::make_unique<GenericTable>();
747    Table->Name = (Twine(Class->getName()) + "sList").str();
748    Table->PreprocessorGuard = Class->getName().upper();
749    Table->CppTypeName = Class->getName();
750
751    for (const RecordVal &Field : Class->getValues()) {
752      std::string FieldName = Field.getName();
753
754      // Skip uninteresting fields: either special to us, or injected
755      // template parameters (if they contain a ':').
756      if (FieldName.find(':') != std::string::npos ||
757          FieldName == "SearchableFields" || FieldName == "EnumNameField" ||
758          FieldName == "EnumValueField")
759        continue;
760
761      Table->Fields.emplace_back(FieldName);
762    }
763
764    collectTableEntries(*Table, Items);
765
766    for (const auto &Field :
767         Class->getValueAsListOfStrings("SearchableFields")) {
768      std::string Name =
769          (Twine("lookup") + Table->CppTypeName + "By" + Field).str();
770      Table->Indices.push_back(parseSearchIndex(*Table, Name, {Field}, false));
771    }
772
773    Tables.emplace_back(std::move(Table));
774  }
775
776  // Emit everything.
777  for (const auto &Enum : Enums)
778    emitGenericEnum(*Enum, OS);
779
780  for (const auto &Table : Tables)
781    emitGenericTable(*Table, OS);
782
783  // Put all #undefs last, to allow multiple sections guarded by the same
784  // define.
785  for (const auto &Guard : PreprocessorGuards)
786    OS << "#undef " << Guard << "\n";
787}
788
789namespace llvm {
790
791void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS) {
792  SearchableTableEmitter(RK).run(OS);
793}
794
795} // End llvm namespace.
796