• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
Twine(NodeKind Kind)165     explicit Twine(NodeKind Kind)
166       : LHSKind(Kind), RHSKind(EmptyKind) {
167       assert(isNullary() && "Invalid kind!");
168     }
169 
170     /// Construct a binary twine.
Twine(const Twine & _LHS,const Twine & _RHS)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.
Twine(Child _LHS,NodeKind _LHSKind,Child _RHS,NodeKind _RHSKind)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 
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 
189     /// isNull - Check for the null twine.
isNull()190     bool isNull() const {
191       return getLHSKind() == NullKind;
192     }
193 
194     /// isEmpty - Check for the empty twine.
isEmpty()195     bool isEmpty() const {
196       return getLHSKind() == EmptyKind;
197     }
198 
199     /// isNullary - Check if this is a nullary twine (null or empty).
isNullary()200     bool isNullary() const {
201       return isNull() || isEmpty();
202     }
203 
204     /// isUnary - Check if this is a unary twine.
isUnary()205     bool isUnary() const {
206       return getRHSKind() == EmptyKind && !isNullary();
207     }
208 
209     /// isBinary - Check if this is a binary twine.
isBinary()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).
isValid()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.
getLHSKind()241     NodeKind getLHSKind() const { return (NodeKind) LHSKind; }
242 
243     /// getRHSKind - Get the NodeKind of the right-hand side.
getRHSKind()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.
Twine()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.
Twine(const char * Str)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.
Twine(const std::string & Str)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.
Twine(const StringRef & Str)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.
Twine(char Val)293     explicit Twine(char Val)
294       : LHSKind(CharKind), RHSKind(EmptyKind) {
295       LHS.character = Val;
296     }
297 
298     /// Construct from a signed char.
Twine(signed char Val)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.
Twine(unsigned char Val)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.
Twine(unsigned Val)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.
Twine(int Val)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.
Twine(const unsigned long & Val)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.
Twine(const long & Val)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.
Twine(const unsigned long long & Val)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.
Twine(const long long & Val)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.
Twine(const char * _LHS,const StringRef & _RHS)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.
Twine(const StringRef & _LHS,const char * _RHS)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.
createNull()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.
utohexstr(const uint64_t & Val)378     static Twine utohexstr(const uint64_t &Val) {
379       Child LHS, RHS;
380       LHS.uHex = &Val;
381       RHS.twine = nullptr;
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.
isTriviallyEmpty()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().
isSingleStringRef()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.
getSingleStringRef()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 
concat(const Twine & Suffix)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
529