llvm/utils/TableGen/Basic/SequenceToOffsetTable.h

   1 //===-- SequenceToOffsetTable.h - Compress similar sequences ----*- C++ -*-===//
   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 // SequenceToOffsetTable can be used to emit a number of null-terminated
  10 // sequences as one big array.  Use the same memory when a sequence is a suffix
  11 // of another.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_UTILS_TABLEGEN_BASIC_SEQUENCETOOFFSETTABLE_H
  16 #define LLVM_UTILS_TABLEGEN_BASIC_SEQUENCETOOFFSETTABLE_H
  17
  18 #include "llvm/ADT/StringExtras.h"
  19 #include "llvm/Support/CommandLine.h"
  20 #include "llvm/Support/raw_ostream.h"
  21 #include <algorithm>
  22 #include <cassert>
  23 #include <functional>
  24 #include <map>
  25
  26 namespace llvm {
  27 extern cl::opt<bool> EmitLongStrLiterals;
  28
  29 inline void printChar(raw_ostream &OS, char C) {
  30   unsigned char UC(C);
  31   if (isAlnum(UC) || isPunct(UC)) {
  32     OS << '\'';
  33     if (C == '\\' || C == '\'')
  34       OS << '\\';
  35     OS << C << '\'';
  36   } else {
  37     OS << unsigned(UC);
  38   }
  39 }
  40
  41 /// SequenceToOffsetTable - Collect a number of terminated sequences of T.
  42 /// Compute the layout of a table that contains all the sequences, possibly by
  43 /// reusing entries.
  44 ///
  45 /// @tparam SeqT The sequence container. (vector or string).
  46 /// @tparam Less A stable comparator for SeqT elements.
  47 template <typename SeqT, typename Less = std::less<typename SeqT::value_type>>
  48 class SequenceToOffsetTable {
  49   typedef typename SeqT::value_type ElemT;
  50
  51   // Define a comparator for SeqT that sorts a suffix immediately before a
  52   // sequence with that suffix.
  53   struct SeqLess {
  54     Less L;
  55     bool operator()(const SeqT &A, const SeqT &B) const {
  56       return std::lexicographical_compare(A.rbegin(), A.rend(), B.rbegin(),
  57                                           B.rend(), L);
  58     }
  59   };
  60
  61   // Keep sequences ordered according to SeqLess so suffixes are easy to find.
  62   // Map each sequence to its offset in the table.
  63   typedef std::map<SeqT, unsigned, SeqLess> SeqMap;
  64
  65   // Sequences added so far, with suffixes removed.
  66   SeqMap Seqs;
  67
  68   // Entries in the final table, or 0 before layout was called.
  69   unsigned Entries;
  70
  71   // isSuffix - Returns true if A is a suffix of B.
  72   static bool isSuffix(const SeqT &A, const SeqT &B) {
  73     return A.size() <= B.size() && std::equal(A.rbegin(), A.rend(), B.rbegin());
  74   }
  75
  76 public:
  77   SequenceToOffsetTable() : Entries(0) {}
  78
  79   /// add - Add a sequence to the table.
  80   /// This must be called before layout().
  81   void add(const SeqT &Seq) {
  82     assert(Entries == 0 && "Cannot call add() after layout()");
  83     typename SeqMap::iterator I = Seqs.lower_bound(Seq);
  84
  85     // If SeqMap contains a sequence that has Seq as a suffix, I will be
  86     // pointing to it.
  87     if (I != Seqs.end() && isSuffix(Seq, I->first))
  88       return;
  89
  90     I = Seqs.insert(I, std::pair(Seq, 0u));
  91
  92     // The entry before I may be a suffix of Seq that can now be erased.
  93     if (I != Seqs.begin() && isSuffix((--I)->first, Seq))
  94       Seqs.erase(I);
  95   }
  96
  97   bool empty() const { return Seqs.empty(); }
  98
  99   unsigned size() const {
 100     assert((empty() || Entries) && "Call layout() before size()");
 101     return Entries;
 102   }
 103
 104   /// layout - Computes the final table layout.
 105   void layout() {
 106     assert(Entries == 0 && "Can only call layout() once");
 107     // Lay out the table in Seqs iteration order.
 108     for (typename SeqMap::iterator I = Seqs.begin(), E = Seqs.end(); I != E;
 109          ++I) {
 110       I->second = Entries;
 111       // Include space for a terminator.
 112       Entries += I->first.size() + 1;
 113     }
 114   }
 115
 116   /// get - Returns the offset of Seq in the final table.
 117   unsigned get(const SeqT &Seq) const {
 118     assert(Entries && "Call layout() before get()");
 119     typename SeqMap::const_iterator I = Seqs.lower_bound(Seq);
 120     assert(I != Seqs.end() && isSuffix(Seq, I->first) &&
 121            "get() called with sequence that wasn't added first");
 122     return I->second + (I->first.size() - Seq.size());
 123   }
 124
 125   /// `emitStringLiteralDef` - Print out the table as the body of an array
 126   /// initializer, where each element is a C string literal terminated by
 127   /// `\0`. Falls back to emitting a comma-separated integer list if
 128   /// `EmitLongStrLiterals` is false
 129   void emitStringLiteralDef(raw_ostream &OS, const Twine &Decl) const {
 130     assert(Entries && "Call layout() before emitStringLiteralDef()");
 131     if (!EmitLongStrLiterals) {
 132       OS << Decl << " = {\n";
 133       emit(OS, printChar, "0");
 134       OS << "  0\n};\n\n";
 135       return;
 136     }
 137
 138     OS << "\n#ifdef __GNUC__\n"
 139        << "#pragma GCC diagnostic push\n"
 140        << "#pragma GCC diagnostic ignored \"-Woverlength-strings\"\n"
 141        << "#endif\n"
 142        << Decl << " = {\n";
 143     for (const auto &[Seq, Offset] : Seqs) {
 144       OS << "  /* " << Offset << " */ \"";
 145       OS.write_escaped(Seq);
 146       OS << "\\0\"\n";
 147     }
 148     OS << "};\n"
 149        << "#ifdef __GNUC__\n"
 150        << "#pragma GCC diagnostic pop\n"
 151        << "#endif\n\n";
 152   }
 153
 154   /// emit - Print out the table as the body of an array initializer.
 155   /// Use the Print function to print elements.
 156   void emit(raw_ostream &OS, void (*Print)(raw_ostream &, ElemT),
 157             const char *Term = "0") const {
 158     assert((empty() || Entries) && "Call layout() before emit()");
 159     for (const auto &[Seq, Offset] : Seqs) {
 160       OS << "  /* " << Offset << " */ ";
 161       for (const ElemT &Element : Seq) {
 162         Print(OS, Element);
 163         OS << ", ";
 164       }
 165       OS << Term << ",\n";
 166     }
 167   }
 168 };
 169
 170 } // end namespace llvm
 171
 172 #endif // LLVM_UTILS_TABLEGEN_BASIC_SEQUENCETOOFFSETTABLE_H