]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===-- Twine.h - Fast Temporary String Concatenation -----------*- C++ -*-===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | ||
10 | #ifndef LLVM_ADT_TWINE_H | |
11 | #define LLVM_ADT_TWINE_H | |
12 | ||
13 | #include "llvm/ADT/StringRef.h" | |
14 | #include "llvm/Support/DataTypes.h" | |
15 | #include "llvm/Support/ErrorHandling.h" | |
16 | #include <cassert> | |
17 | #include <string> | |
18 | ||
19 | namespace llvm { | |
20 | template <typename T> | |
21 | class SmallVectorImpl; | |
22 | class StringRef; | |
23 | class raw_ostream; | |
24 | ||
25 | /// Twine - A lightweight data structure for efficiently representing the | |
26 | /// concatenation of temporary values as strings. | |
27 | /// | |
28 | /// A Twine is a kind of rope, it represents a concatenated string using a | |
29 | /// binary-tree, where the string is the preorder of the nodes. Since the | |
30 | /// Twine can be efficiently rendered into a buffer when its result is used, | |
31 | /// it avoids the cost of generating temporary values for intermediate string | |
32 | /// results -- particularly in cases when the Twine result is never | |
33 | /// required. By explicitly tracking the type of leaf nodes, we can also avoid | |
34 | /// the creation of temporary strings for conversions operations (such as | |
35 | /// appending an integer to a string). | |
36 | /// | |
37 | /// A Twine is not intended for use directly and should not be stored, its | |
38 | /// implementation relies on the ability to store pointers to temporary stack | |
39 | /// objects which may be deallocated at the end of a statement. Twines should | |
40 | /// only be used accepted as const references in arguments, when an API wishes | |
41 | /// to accept possibly-concatenated strings. | |
42 | /// | |
43 | /// Twines support a special 'null' value, which always concatenates to form | |
44 | /// itself, and renders as an empty string. This can be returned from APIs to | |
45 | /// effectively nullify any concatenations performed on the result. | |
46 | /// | |
47 | /// \b Implementation | |
48 | /// | |
49 | /// Given the nature of a Twine, it is not possible for the Twine's | |
50 | /// concatenation method to construct interior nodes; the result must be | |
51 | /// represented inside the returned value. For this reason a Twine object | |
52 | /// actually holds two values, the left- and right-hand sides of a | |
53 | /// concatenation. We also have nullary Twine objects, which are effectively | |
54 | /// sentinel values that represent empty strings. | |
55 | /// | |
56 | /// Thus, a Twine can effectively have zero, one, or two children. The \see | |
57 | /// isNullary(), \see isUnary(), and \see isBinary() predicates exist for | |
58 | /// testing the number of children. | |
59 | /// | |
60 | /// We maintain a number of invariants on Twine objects (FIXME: Why): | |
61 | /// - Nullary twines are always represented with their Kind on the left-hand | |
62 | /// side, and the Empty kind on the right-hand side. | |
63 | /// - Unary twines are always represented with the value on the left-hand | |
64 | /// side, and the Empty kind on the right-hand side. | |
65 | /// - If a Twine has another Twine as a child, that child should always be | |
66 | /// binary (otherwise it could have been folded into the parent). | |
67 | /// | |
68 | /// These invariants are check by \see isValid(). | |
69 | /// | |
70 | /// \b Efficiency Considerations | |
71 | /// | |
72 | /// The Twine is designed to yield efficient and small code for common | |
73 | /// situations. For this reason, the concat() method is inlined so that | |
74 | /// concatenations of leaf nodes can be optimized into stores directly into a | |
75 | /// single stack allocated object. | |
76 | /// | |
77 | /// In practice, not all compilers can be trusted to optimize concat() fully, | |
78 | /// so we provide two additional methods (and accompanying operator+ | |
79 | /// overloads) to guarantee that particularly important cases (cstring plus | |
80 | /// StringRef) codegen as desired. | |
81 | class Twine { | |
82 | /// NodeKind - Represent the type of an argument. | |
83 | enum NodeKind { | |
84 | /// An empty string; the result of concatenating anything with it is also | |
85 | /// empty. | |
86 | NullKind, | |
87 | ||
88 | /// The empty string. | |
89 | EmptyKind, | |
90 | ||
91 | /// A pointer to a Twine instance. | |
92 | TwineKind, | |
93 | ||
94 | /// A pointer to a C string instance. | |
95 | CStringKind, | |
96 | ||
97 | /// A pointer to an std::string instance. | |
98 | StdStringKind, | |
99 | ||
100 | /// A pointer to a StringRef instance. | |
101 | StringRefKind, | |
102 | ||
103 | /// A char value reinterpreted as a pointer, to render as a character. | |
104 | CharKind, | |
105 | ||
106 | /// An unsigned int value reinterpreted as a pointer, to render as an | |
107 | /// unsigned decimal integer. | |
108 | DecUIKind, | |
109 | ||
110 | /// An int value reinterpreted as a pointer, to render as a signed | |
111 | /// decimal integer. | |
112 | DecIKind, | |
113 | ||
114 | /// A pointer to an unsigned long value, to render as an unsigned decimal | |
115 | /// integer. | |
116 | DecULKind, | |
117 | ||
118 | /// A pointer to a long value, to render as a signed decimal integer. | |
119 | DecLKind, | |
120 | ||
121 | /// A pointer to an unsigned long long value, to render as an unsigned | |
122 | /// decimal integer. | |
123 | DecULLKind, | |
124 | ||
125 | /// A pointer to a long long value, to render as a signed decimal integer. | |
126 | DecLLKind, | |
127 | ||
128 | /// A pointer to a uint64_t value, to render as an unsigned hexadecimal | |
129 | /// integer. | |
130 | UHexKind | |
131 | }; | |
132 | ||
133 | union Child | |
134 | { | |
135 | const Twine *twine; | |
136 | const char *cString; | |
137 | const std::string *stdString; | |
138 | const StringRef *stringRef; | |
139 | char character; | |
140 | unsigned int decUI; | |
141 | int decI; | |
142 | const unsigned long *decUL; | |
143 | const long *decL; | |
144 | const unsigned long long *decULL; | |
145 | const long long *decLL; | |
146 | const uint64_t *uHex; | |
147 | }; | |
148 | ||
149 | private: | |
150 | /// LHS - The prefix in the concatenation, which may be uninitialized for | |
151 | /// Null or Empty kinds. | |
152 | Child LHS; | |
153 | /// RHS - The suffix in the concatenation, which may be uninitialized for | |
154 | /// Null or Empty kinds. | |
155 | Child RHS; | |
156 | // enums stored as unsigned chars to save on space while some compilers | |
157 | // don't support specifying the backing type for an enum | |
158 | /// LHSKind - The NodeKind of the left hand side, \see getLHSKind(). | |
159 | unsigned char LHSKind; | |
160 | /// RHSKind - The NodeKind of the left hand side, \see getLHSKind(). | |
161 | unsigned char RHSKind; | |
162 | ||
163 | private: | |
164 | /// Construct a nullary twine; the kind must be NullKind or EmptyKind. | |
165 | explicit Twine(NodeKind Kind) | |
166 | : LHSKind(Kind), RHSKind(EmptyKind) { | |
167 | assert(isNullary() && "Invalid kind!"); | |
168 | } | |
169 | ||
170 | /// Construct a binary twine. | |
171 | explicit Twine(const Twine &_LHS, const Twine &_RHS) | |
172 | : LHSKind(TwineKind), RHSKind(TwineKind) { | |
173 | LHS.twine = &_LHS; | |
174 | RHS.twine = &_RHS; | |
175 | assert(isValid() && "Invalid twine!"); | |
176 | } | |
177 | ||
178 | /// Construct a twine from explicit values. | |
179 | explicit Twine(Child _LHS, NodeKind _LHSKind, | |
180 | Child _RHS, NodeKind _RHSKind) | |
181 | : LHS(_LHS), RHS(_RHS), LHSKind(_LHSKind), RHSKind(_RHSKind) { | |
182 | assert(isValid() && "Invalid twine!"); | |
183 | } | |
184 | ||
1a4d82fc JJ |
185 | /// Since the intended use of twines is as temporary objects, assignments |
186 | /// when concatenating might cause undefined behavior or stack corruptions | |
187 | Twine &operator=(const Twine &Other) LLVM_DELETED_FUNCTION; | |
188 | ||
223e47cc LB |
189 | /// isNull - Check for the null twine. |
190 | bool isNull() const { | |
191 | return getLHSKind() == NullKind; | |
192 | } | |
193 | ||
194 | /// isEmpty - Check for the empty twine. | |
195 | bool isEmpty() const { | |
196 | return getLHSKind() == EmptyKind; | |
197 | } | |
198 | ||
199 | /// isNullary - Check if this is a nullary twine (null or empty). | |
200 | bool isNullary() const { | |
201 | return isNull() || isEmpty(); | |
202 | } | |
203 | ||
204 | /// isUnary - Check if this is a unary twine. | |
205 | bool isUnary() const { | |
206 | return getRHSKind() == EmptyKind && !isNullary(); | |
207 | } | |
208 | ||
209 | /// isBinary - Check if this is a binary twine. | |
210 | bool isBinary() const { | |
211 | return getLHSKind() != NullKind && getRHSKind() != EmptyKind; | |
212 | } | |
213 | ||
214 | /// isValid - Check if this is a valid twine (satisfying the invariants on | |
215 | /// order and number of arguments). | |
216 | bool isValid() const { | |
217 | // Nullary twines always have Empty on the RHS. | |
218 | if (isNullary() && getRHSKind() != EmptyKind) | |
219 | return false; | |
220 | ||
221 | // Null should never appear on the RHS. | |
222 | if (getRHSKind() == NullKind) | |
223 | return false; | |
224 | ||
225 | // The RHS cannot be non-empty if the LHS is empty. | |
226 | if (getRHSKind() != EmptyKind && getLHSKind() == EmptyKind) | |
227 | return false; | |
228 | ||
229 | // A twine child should always be binary. | |
230 | if (getLHSKind() == TwineKind && | |
231 | !LHS.twine->isBinary()) | |
232 | return false; | |
233 | if (getRHSKind() == TwineKind && | |
234 | !RHS.twine->isBinary()) | |
235 | return false; | |
236 | ||
237 | return true; | |
238 | } | |
239 | ||
240 | /// getLHSKind - Get the NodeKind of the left-hand side. | |
241 | NodeKind getLHSKind() const { return (NodeKind) LHSKind; } | |
242 | ||
1a4d82fc | 243 | /// getRHSKind - Get the NodeKind of the right-hand side. |
223e47cc LB |
244 | NodeKind getRHSKind() const { return (NodeKind) RHSKind; } |
245 | ||
246 | /// printOneChild - Print one child from a twine. | |
247 | void printOneChild(raw_ostream &OS, Child Ptr, NodeKind Kind) const; | |
248 | ||
249 | /// printOneChildRepr - Print the representation of one child from a twine. | |
250 | void printOneChildRepr(raw_ostream &OS, Child Ptr, | |
251 | NodeKind Kind) const; | |
252 | ||
253 | public: | |
254 | /// @name Constructors | |
255 | /// @{ | |
256 | ||
257 | /// Construct from an empty string. | |
258 | /*implicit*/ Twine() : LHSKind(EmptyKind), RHSKind(EmptyKind) { | |
259 | assert(isValid() && "Invalid twine!"); | |
260 | } | |
261 | ||
262 | /// Construct from a C string. | |
263 | /// | |
264 | /// We take care here to optimize "" into the empty twine -- this will be | |
265 | /// optimized out for string constants. This allows Twine arguments have | |
266 | /// default "" values, without introducing unnecessary string constants. | |
267 | /*implicit*/ Twine(const char *Str) | |
268 | : RHSKind(EmptyKind) { | |
269 | if (Str[0] != '\0') { | |
270 | LHS.cString = Str; | |
271 | LHSKind = CStringKind; | |
272 | } else | |
273 | LHSKind = EmptyKind; | |
274 | ||
275 | assert(isValid() && "Invalid twine!"); | |
276 | } | |
277 | ||
278 | /// Construct from an std::string. | |
279 | /*implicit*/ Twine(const std::string &Str) | |
280 | : LHSKind(StdStringKind), RHSKind(EmptyKind) { | |
281 | LHS.stdString = &Str; | |
282 | assert(isValid() && "Invalid twine!"); | |
283 | } | |
284 | ||
285 | /// Construct from a StringRef. | |
286 | /*implicit*/ Twine(const StringRef &Str) | |
287 | : LHSKind(StringRefKind), RHSKind(EmptyKind) { | |
288 | LHS.stringRef = &Str; | |
289 | assert(isValid() && "Invalid twine!"); | |
290 | } | |
291 | ||
292 | /// Construct from a char. | |
293 | explicit Twine(char Val) | |
294 | : LHSKind(CharKind), RHSKind(EmptyKind) { | |
295 | LHS.character = Val; | |
296 | } | |
297 | ||
298 | /// Construct from a signed char. | |
299 | explicit Twine(signed char Val) | |
300 | : LHSKind(CharKind), RHSKind(EmptyKind) { | |
301 | LHS.character = static_cast<char>(Val); | |
302 | } | |
303 | ||
304 | /// Construct from an unsigned char. | |
305 | explicit Twine(unsigned char Val) | |
306 | : LHSKind(CharKind), RHSKind(EmptyKind) { | |
307 | LHS.character = static_cast<char>(Val); | |
308 | } | |
309 | ||
310 | /// Construct a twine to print \p Val as an unsigned decimal integer. | |
311 | explicit Twine(unsigned Val) | |
312 | : LHSKind(DecUIKind), RHSKind(EmptyKind) { | |
313 | LHS.decUI = Val; | |
314 | } | |
315 | ||
316 | /// Construct a twine to print \p Val as a signed decimal integer. | |
317 | explicit Twine(int Val) | |
318 | : LHSKind(DecIKind), RHSKind(EmptyKind) { | |
319 | LHS.decI = Val; | |
320 | } | |
321 | ||
322 | /// Construct a twine to print \p Val as an unsigned decimal integer. | |
323 | explicit Twine(const unsigned long &Val) | |
324 | : LHSKind(DecULKind), RHSKind(EmptyKind) { | |
325 | LHS.decUL = &Val; | |
326 | } | |
327 | ||
328 | /// Construct a twine to print \p Val as a signed decimal integer. | |
329 | explicit Twine(const long &Val) | |
330 | : LHSKind(DecLKind), RHSKind(EmptyKind) { | |
331 | LHS.decL = &Val; | |
332 | } | |
333 | ||
334 | /// Construct a twine to print \p Val as an unsigned decimal integer. | |
335 | explicit Twine(const unsigned long long &Val) | |
336 | : LHSKind(DecULLKind), RHSKind(EmptyKind) { | |
337 | LHS.decULL = &Val; | |
338 | } | |
339 | ||
340 | /// Construct a twine to print \p Val as a signed decimal integer. | |
341 | explicit Twine(const long long &Val) | |
342 | : LHSKind(DecLLKind), RHSKind(EmptyKind) { | |
343 | LHS.decLL = &Val; | |
344 | } | |
345 | ||
346 | // FIXME: Unfortunately, to make sure this is as efficient as possible we | |
347 | // need extra binary constructors from particular types. We can't rely on | |
348 | // the compiler to be smart enough to fold operator+()/concat() down to the | |
349 | // right thing. Yet. | |
350 | ||
351 | /// Construct as the concatenation of a C string and a StringRef. | |
352 | /*implicit*/ Twine(const char *_LHS, const StringRef &_RHS) | |
353 | : LHSKind(CStringKind), RHSKind(StringRefKind) { | |
354 | LHS.cString = _LHS; | |
355 | RHS.stringRef = &_RHS; | |
356 | assert(isValid() && "Invalid twine!"); | |
357 | } | |
358 | ||
359 | /// Construct as the concatenation of a StringRef and a C string. | |
360 | /*implicit*/ Twine(const StringRef &_LHS, const char *_RHS) | |
361 | : LHSKind(StringRefKind), RHSKind(CStringKind) { | |
362 | LHS.stringRef = &_LHS; | |
363 | RHS.cString = _RHS; | |
364 | assert(isValid() && "Invalid twine!"); | |
365 | } | |
366 | ||
367 | /// Create a 'null' string, which is an empty string that always | |
368 | /// concatenates to form another empty string. | |
369 | static Twine createNull() { | |
370 | return Twine(NullKind); | |
371 | } | |
372 | ||
373 | /// @} | |
374 | /// @name Numeric Conversions | |
375 | /// @{ | |
376 | ||
377 | // Construct a twine to print \p Val as an unsigned hexadecimal integer. | |
378 | static Twine utohexstr(const uint64_t &Val) { | |
379 | Child LHS, RHS; | |
380 | LHS.uHex = &Val; | |
1a4d82fc | 381 | RHS.twine = nullptr; |
223e47cc LB |
382 | return Twine(LHS, UHexKind, RHS, EmptyKind); |
383 | } | |
384 | ||
385 | /// @} | |
386 | /// @name Predicate Operations | |
387 | /// @{ | |
388 | ||
389 | /// isTriviallyEmpty - Check if this twine is trivially empty; a false | |
390 | /// return value does not necessarily mean the twine is empty. | |
391 | bool isTriviallyEmpty() const { | |
392 | return isNullary(); | |
393 | } | |
394 | ||
395 | /// isSingleStringRef - Return true if this twine can be dynamically | |
396 | /// accessed as a single StringRef value with getSingleStringRef(). | |
397 | bool isSingleStringRef() const { | |
398 | if (getRHSKind() != EmptyKind) return false; | |
399 | ||
400 | switch (getLHSKind()) { | |
401 | case EmptyKind: | |
402 | case CStringKind: | |
403 | case StdStringKind: | |
404 | case StringRefKind: | |
405 | return true; | |
406 | default: | |
407 | return false; | |
408 | } | |
409 | } | |
410 | ||
411 | /// @} | |
412 | /// @name String Operations | |
413 | /// @{ | |
414 | ||
415 | Twine concat(const Twine &Suffix) const; | |
416 | ||
417 | /// @} | |
418 | /// @name Output & Conversion. | |
419 | /// @{ | |
420 | ||
421 | /// str - Return the twine contents as a std::string. | |
422 | std::string str() const; | |
423 | ||
424 | /// toVector - Write the concatenated string into the given SmallString or | |
425 | /// SmallVector. | |
426 | void toVector(SmallVectorImpl<char> &Out) const; | |
427 | ||
428 | /// getSingleStringRef - This returns the twine as a single StringRef. This | |
429 | /// method is only valid if isSingleStringRef() is true. | |
430 | StringRef getSingleStringRef() const { | |
431 | assert(isSingleStringRef() &&"This cannot be had as a single stringref!"); | |
432 | switch (getLHSKind()) { | |
433 | default: llvm_unreachable("Out of sync with isSingleStringRef"); | |
434 | case EmptyKind: return StringRef(); | |
435 | case CStringKind: return StringRef(LHS.cString); | |
436 | case StdStringKind: return StringRef(*LHS.stdString); | |
437 | case StringRefKind: return *LHS.stringRef; | |
438 | } | |
439 | } | |
440 | ||
441 | /// toStringRef - This returns the twine as a single StringRef if it can be | |
442 | /// represented as such. Otherwise the twine is written into the given | |
443 | /// SmallVector and a StringRef to the SmallVector's data is returned. | |
444 | StringRef toStringRef(SmallVectorImpl<char> &Out) const; | |
445 | ||
446 | /// toNullTerminatedStringRef - This returns the twine as a single null | |
447 | /// terminated StringRef if it can be represented as such. Otherwise the | |
448 | /// twine is written into the given SmallVector and a StringRef to the | |
449 | /// SmallVector's data is returned. | |
450 | /// | |
451 | /// The returned StringRef's size does not include the null terminator. | |
452 | StringRef toNullTerminatedStringRef(SmallVectorImpl<char> &Out) const; | |
453 | ||
454 | /// Write the concatenated string represented by this twine to the | |
455 | /// stream \p OS. | |
456 | void print(raw_ostream &OS) const; | |
457 | ||
458 | /// Dump the concatenated string represented by this twine to stderr. | |
459 | void dump() const; | |
460 | ||
461 | /// Write the representation of this twine to the stream \p OS. | |
462 | void printRepr(raw_ostream &OS) const; | |
463 | ||
464 | /// Dump the representation of this twine to stderr. | |
465 | void dumpRepr() const; | |
466 | ||
467 | /// @} | |
468 | }; | |
469 | ||
470 | /// @name Twine Inline Implementations | |
471 | /// @{ | |
472 | ||
473 | inline Twine Twine::concat(const Twine &Suffix) const { | |
474 | // Concatenation with null is null. | |
475 | if (isNull() || Suffix.isNull()) | |
476 | return Twine(NullKind); | |
477 | ||
478 | // Concatenation with empty yields the other side. | |
479 | if (isEmpty()) | |
480 | return Suffix; | |
481 | if (Suffix.isEmpty()) | |
482 | return *this; | |
483 | ||
484 | // Otherwise we need to create a new node, taking care to fold in unary | |
485 | // twines. | |
486 | Child NewLHS, NewRHS; | |
487 | NewLHS.twine = this; | |
488 | NewRHS.twine = &Suffix; | |
489 | NodeKind NewLHSKind = TwineKind, NewRHSKind = TwineKind; | |
490 | if (isUnary()) { | |
491 | NewLHS = LHS; | |
492 | NewLHSKind = getLHSKind(); | |
493 | } | |
494 | if (Suffix.isUnary()) { | |
495 | NewRHS = Suffix.LHS; | |
496 | NewRHSKind = Suffix.getLHSKind(); | |
497 | } | |
498 | ||
499 | return Twine(NewLHS, NewLHSKind, NewRHS, NewRHSKind); | |
500 | } | |
501 | ||
502 | inline Twine operator+(const Twine &LHS, const Twine &RHS) { | |
503 | return LHS.concat(RHS); | |
504 | } | |
505 | ||
506 | /// Additional overload to guarantee simplified codegen; this is equivalent to | |
507 | /// concat(). | |
508 | ||
509 | inline Twine operator+(const char *LHS, const StringRef &RHS) { | |
510 | return Twine(LHS, RHS); | |
511 | } | |
512 | ||
513 | /// Additional overload to guarantee simplified codegen; this is equivalent to | |
514 | /// concat(). | |
515 | ||
516 | inline Twine operator+(const StringRef &LHS, const char *RHS) { | |
517 | return Twine(LHS, RHS); | |
518 | } | |
519 | ||
520 | inline raw_ostream &operator<<(raw_ostream &OS, const Twine &RHS) { | |
521 | RHS.print(OS); | |
522 | return OS; | |
523 | } | |
524 | ||
525 | /// @} | |
526 | } | |
527 | ||
528 | #endif |