llvm/utils/TableGen/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_SEQUENCETOOFFSETTABLE_H
  16 #define LLVM_UTILS_TABLEGEN_SEQUENCETOOFFSETTABLE_H
  17
  18 #include "llvm/Support/CommandLine.h"
  19 #include "llvm/Support/raw_ostream.h"
  20 #include <algorithm>
  21 #include <cassert>
  22 #include <cctype>
  23 #include <functional>
  24 #include <map>
  25
  26 namespace llvm {
  27 extern llvm::cl::opt<bool> EmitLongStrLiterals;
  28
  29 // Helper function for SequenceToOffsetTable<string>.
  30 static inline void printStrLitEscChar(raw_ostream &OS, char C) {
  31   const char *Escapes[] = {
  32       "\\000", "\\001", "\\002", "\\003", "\\004", "\\005", "\\006", "\\007",
  33       "\\010", "\\t",   "\\n",   "\\013", "\\014", "\\r",   "\\016", "\\017",
  34       "\\020", "\\021", "\\022", "\\023", "\\024", "\\025", "\\026", "\\027",
  35       "\\030", "\\031", "\\032", "\\033", "\\034", "\\035", "\\036", "\\037",
  36       " ",     "!",     "\\\"",  "#",     "$",     "%",     "&",     "'",
  37       "(",     ")",     "*",     "+",     ",",     "-",     ".",     "/",
  38       "0",     "1",     "2",     "3",     "4",     "5",     "6",     "7",
  39       "8",     "9",     ":",     ";",     "<",     "=",     ">",     "?",
  40       "@",     "A",     "B",     "C",     "D",     "E",     "F",     "G",
  41       "H",     "I",     "J",     "K",     "L",     "M",     "N",     "O",
  42       "P",     "Q",     "R",     "S",     "T",     "U",     "V",     "W",
  43       "X",     "Y",     "Z",     "[",     "\\\\",  "]",     "^",     "_",
  44       "`",     "a",     "b",     "c",     "d",     "e",     "f",     "g",
  45       "h",     "i",     "j",     "k",     "l",     "m",     "n",     "o",
  46       "p",     "q",     "r",     "s",     "t",     "u",     "v",     "w",
  47       "x",     "y",     "z",     "{",     "|",     "}",     "~",     "\\177",
  48       "\\200", "\\201", "\\202", "\\203", "\\204", "\\205", "\\206", "\\207",
  49       "\\210", "\\211", "\\212", "\\213", "\\214", "\\215", "\\216", "\\217",
  50       "\\220", "\\221", "\\222", "\\223", "\\224", "\\225", "\\226", "\\227",
  51       "\\230", "\\231", "\\232", "\\233", "\\234", "\\235", "\\236", "\\237",
  52       "\\240", "\\241", "\\242", "\\243", "\\244", "\\245", "\\246", "\\247",
  53       "\\250", "\\251", "\\252", "\\253", "\\254", "\\255", "\\256", "\\257",
  54       "\\260", "\\261", "\\262", "\\263", "\\264", "\\265", "\\266", "\\267",
  55       "\\270", "\\271", "\\272", "\\273", "\\274", "\\275", "\\276", "\\277",
  56       "\\300", "\\301", "\\302", "\\303", "\\304", "\\305", "\\306", "\\307",
  57       "\\310", "\\311", "\\312", "\\313", "\\314", "\\315", "\\316", "\\317",
  58       "\\320", "\\321", "\\322", "\\323", "\\324", "\\325", "\\326", "\\327",
  59       "\\330", "\\331", "\\332", "\\333", "\\334", "\\335", "\\336", "\\337",
  60       "\\340", "\\341", "\\342", "\\343", "\\344", "\\345", "\\346", "\\347",
  61       "\\350", "\\351", "\\352", "\\353", "\\354", "\\355", "\\356", "\\357",
  62       "\\360", "\\361", "\\362", "\\363", "\\364", "\\365", "\\366", "\\367",
  63       "\\370", "\\371", "\\372", "\\373", "\\374", "\\375", "\\376", "\\377"};
  64
  65   static_assert(sizeof Escapes / sizeof Escapes[0] ==
  66                     std::numeric_limits<unsigned char>::max() + 1,
  67                 "unsupported character type");
  68   OS << Escapes[static_cast<unsigned char>(C)];
  69 }
  70
  71 static inline void printChar(raw_ostream &OS, char C) {
  72   unsigned char UC(C);
  73   if (isalnum(UC) || ispunct(UC)) {
  74     OS << '\'';
  75     if (C == '\\' || C == '\'')
  76       OS << '\\';
  77     OS << C << '\'';
  78   } else {
  79     OS << unsigned(UC);
  80   }
  81 }
  82
  83 /// SequenceToOffsetTable - Collect a number of terminated sequences of T.
  84 /// Compute the layout of a table that contains all the sequences, possibly by
  85 /// reusing entries.
  86 ///
  87 /// @tparam SeqT The sequence container. (vector or string).
  88 /// @tparam Less A stable comparator for SeqT elements.
  89 template<typename SeqT, typename Less = std::less<typename SeqT::value_type> >
  90 class SequenceToOffsetTable {
  91   typedef typename SeqT::value_type ElemT;
  92
  93   // Define a comparator for SeqT that sorts a suffix immediately before a
  94   // sequence with that suffix.
  95   struct SeqLess {
  96     Less L;
  97     bool operator()(const SeqT &A, const SeqT &B) const {
  98       return std::lexicographical_compare(A.rbegin(), A.rend(),
  99                                           B.rbegin(), B.rend(), L);
 100     }
 101   };
 102
 103   // Keep sequences ordered according to SeqLess so suffixes are easy to find.
 104   // Map each sequence to its offset in the table.
 105   typedef std::map<SeqT, unsigned, SeqLess> SeqMap;
 106
 107   // Sequences added so far, with suffixes removed.
 108   SeqMap Seqs;
 109
 110   // Entries in the final table, or 0 before layout was called.
 111   unsigned Entries;
 112
 113   // isSuffix - Returns true if A is a suffix of B.
 114   static bool isSuffix(const SeqT &A, const SeqT &B) {
 115     return A.size() <= B.size() && std::equal(A.rbegin(), A.rend(), B.rbegin());
 116   }
 117
 118 public:
 119   SequenceToOffsetTable() : Entries(0) {}
 120
 121   /// add - Add a sequence to the table.
 122   /// This must be called before layout().
 123   void add(const SeqT &Seq) {
 124     assert(Entries == 0 && "Cannot call add() after layout()");
 125     typename SeqMap::iterator I = Seqs.lower_bound(Seq);
 126
 127     // If SeqMap contains a sequence that has Seq as a suffix, I will be
 128     // pointing to it.
 129     if (I != Seqs.end() && isSuffix(Seq, I->first))
 130       return;
 131
 132     I = Seqs.insert(I, std::make_pair(Seq, 0u));
 133
 134     // The entry before I may be a suffix of Seq that can now be erased.
 135     if (I != Seqs.begin() && isSuffix((--I)->first, Seq))
 136       Seqs.erase(I);
 137   }
 138
 139   bool empty() const { return Seqs.empty(); }
 140
 141   unsigned size() const {
 142     assert((empty() || Entries) && "Call layout() before size()");
 143     return Entries;
 144   }
 145
 146   /// layout - Computes the final table layout.
 147   void layout() {
 148     assert(Entries == 0 && "Can only call layout() once");
 149     // Lay out the table in Seqs iteration order.
 150     for (typename SeqMap::iterator I = Seqs.begin(), E = Seqs.end(); I != E;
 151          ++I) {
 152       I->second = Entries;
 153       // Include space for a terminator.
 154       Entries += I->first.size() + 1;
 155     }
 156   }
 157
 158   /// get - Returns the offset of Seq in the final table.
 159   unsigned get(const SeqT &Seq) const {
 160     assert(Entries && "Call layout() before get()");
 161     typename SeqMap::const_iterator I = Seqs.lower_bound(Seq);
 162     assert(I != Seqs.end() && isSuffix(Seq, I->first) &&
 163            "get() called with sequence that wasn't added first");
 164     return I->second + (I->first.size() - Seq.size());
 165   }
 166
 167   /// `emitStringLiteralDef` - Print out the table as the body of an array
 168   /// initializer, where each element is a C string literal terminated by
 169   /// `\0`. Falls back to emitting a comma-separated integer list if
 170   /// `EmitLongStrLiterals` is false
 171   void emitStringLiteralDef(raw_ostream &OS, const llvm::Twine &Decl) const {
 172     assert(Entries && "Call layout() before emitStringLiteralDef()");
 173     if (EmitLongStrLiterals) {
 174       OS << "\n#ifdef __GNUC__\n"
 175          << "#pragma GCC diagnostic push\n"
 176          << "#pragma GCC diagnostic ignored \"-Woverlength-strings\"\n"
 177          << "#endif\n"
 178          << Decl << " = {\n";
 179     } else {
 180       OS << Decl << " = {\n";
 181       emit(OS, printChar, "0");
 182       OS << "\n};\n\n";
 183       return;
 184     }
 185     for (auto I : Seqs) {
 186       OS << "  /* " << I.second << " */ \"";
 187       for (auto C : I.first) {
 188         printStrLitEscChar(OS, C);
 189       }
 190       OS << "\\0\"\n";
 191     }
 192     OS << "};\n"
 193        << "#ifdef __GNUC__\n"
 194        << "#pragma GCC diagnostic pop\n"
 195        << "#endif\n\n";
 196   }
 197
 198   /// emit - Print out the table as the body of an array initializer.
 199   /// Use the Print function to print elements.
 200   void emit(raw_ostream &OS,
 201             void (*Print)(raw_ostream&, ElemT),
 202             const char *Term = "0") const {
 203     assert((empty() || Entries) && "Call layout() before emit()");
 204     for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end();
 205          I != E; ++I) {
 206       OS << "  /* " << I->second << " */ ";
 207       for (typename SeqT::const_iterator SI = I->first.begin(),
 208              SE = I->first.end(); SI != SE; ++SI) {
 209         Print(OS, *SI);
 210         OS << ", ";
 211       }
 212       OS << Term << ",\n";
 213     }
 214   }
 215 };
 216
 217 } // end namespace llvm
 218
 219 #endif