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
26namespace llvm {
27extern llvm::cl::opt<bool> EmitLongStrLiterals;
28
29static 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.
47template <typename SeqT, typename Less = std::less<typename SeqT::value_type>>
48class 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
76public:
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(A: Seq, B: 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(A: (--I)->first, B: 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 llvm::Twine &Decl) const {
130 assert(Entries && "Call layout() before emitStringLiteralDef()");
131 if (!EmitLongStrLiterals) {
132 OS << Decl << " = {\n";
133 emit(OS, Print: printChar, Term: "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 (auto I : Seqs) {
144 OS << " /* " << I.second << " */ \"";
145 OS.write_escaped(Str: I.first);
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 (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end();
160 I != E; ++I) {
161 OS << " /* " << I->second << " */ ";
162 for (typename SeqT::const_iterator SI = I->first.begin(),
163 SE = I->first.end();
164 SI != SE; ++SI) {
165 Print(OS, *SI);
166 OS << ", ";
167 }
168 OS << Term << ",\n";
169 }
170 }
171};
172
173} // end namespace llvm
174
175#endif
176