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 << Decl << " = {\n"; 175 emit(OS, printChar, "0"); 176 OS << " 0\n};\n\n"; 177 return; 178 } 179 180 OS << "\n#ifdef __GNUC__\n" 181 << "#pragma GCC diagnostic push\n" 182 << "#pragma GCC diagnostic ignored \"-Woverlength-strings\"\n" 183 << "#endif\n" 184 << Decl << " = {\n"; 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 220