Home | History | Annotate | Download | only in ADT
      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 
    185     /// isNull - Check for the null twine.
    186     bool isNull() const {
    187       return getLHSKind() == NullKind;
    188     }
    189 
    190     /// isEmpty - Check for the empty twine.
    191     bool isEmpty() const {
    192       return getLHSKind() == EmptyKind;
    193     }
    194 
    195     /// isNullary - Check if this is a nullary twine (null or empty).
    196     bool isNullary() const {
    197       return isNull() || isEmpty();
    198     }
    199 
    200     /// isUnary - Check if this is a unary twine.
    201     bool isUnary() const {
    202       return getRHSKind() == EmptyKind && !isNullary();
    203     }
    204 
    205     /// isBinary - Check if this is a binary twine.
    206     bool isBinary() const {
    207       return getLHSKind() != NullKind && getRHSKind() != EmptyKind;
    208     }
    209 
    210     /// isValid - Check if this is a valid twine (satisfying the invariants on
    211     /// order and number of arguments).
    212     bool isValid() const {
    213       // Nullary twines always have Empty on the RHS.
    214       if (isNullary() && getRHSKind() != EmptyKind)
    215         return false;
    216 
    217       // Null should never appear on the RHS.
    218       if (getRHSKind() == NullKind)
    219         return false;
    220 
    221       // The RHS cannot be non-empty if the LHS is empty.
    222       if (getRHSKind() != EmptyKind && getLHSKind() == EmptyKind)
    223         return false;
    224 
    225       // A twine child should always be binary.
    226       if (getLHSKind() == TwineKind &&
    227           !LHS.twine->isBinary())
    228         return false;
    229       if (getRHSKind() == TwineKind &&
    230           !RHS.twine->isBinary())
    231         return false;
    232 
    233       return true;
    234     }
    235 
    236     /// getLHSKind - Get the NodeKind of the left-hand side.
    237     NodeKind getLHSKind() const { return (NodeKind) LHSKind; }
    238 
    239     /// getRHSKind - Get the NodeKind of the right-hand side.
    240     NodeKind getRHSKind() const { return (NodeKind) RHSKind; }
    241 
    242     /// printOneChild - Print one child from a twine.
    243     void printOneChild(raw_ostream &OS, Child Ptr, NodeKind Kind) const;
    244 
    245     /// printOneChildRepr - Print the representation of one child from a twine.
    246     void printOneChildRepr(raw_ostream &OS, Child Ptr,
    247                            NodeKind Kind) const;
    248 
    249   public:
    250     /// @name Constructors
    251     /// @{
    252 
    253     /// Construct from an empty string.
    254     /*implicit*/ Twine() : LHSKind(EmptyKind), RHSKind(EmptyKind) {
    255       assert(isValid() && "Invalid twine!");
    256     }
    257 
    258     /// Construct from a C string.
    259     ///
    260     /// We take care here to optimize "" into the empty twine -- this will be
    261     /// optimized out for string constants. This allows Twine arguments have
    262     /// default "" values, without introducing unnecessary string constants.
    263     /*implicit*/ Twine(const char *Str)
    264       : RHSKind(EmptyKind) {
    265       if (Str[0] != '\0') {
    266         LHS.cString = Str;
    267         LHSKind = CStringKind;
    268       } else
    269         LHSKind = EmptyKind;
    270 
    271       assert(isValid() && "Invalid twine!");
    272     }
    273 
    274     /// Construct from an std::string.
    275     /*implicit*/ Twine(const std::string &Str)
    276       : LHSKind(StdStringKind), RHSKind(EmptyKind) {
    277       LHS.stdString = &Str;
    278       assert(isValid() && "Invalid twine!");
    279     }
    280 
    281     /// Construct from a StringRef.
    282     /*implicit*/ Twine(const StringRef &Str)
    283       : LHSKind(StringRefKind), RHSKind(EmptyKind) {
    284       LHS.stringRef = &Str;
    285       assert(isValid() && "Invalid twine!");
    286     }
    287 
    288     /// Construct from a char.
    289     explicit Twine(char Val)
    290       : LHSKind(CharKind), RHSKind(EmptyKind) {
    291       LHS.character = Val;
    292     }
    293 
    294     /// Construct from a signed char.
    295     explicit Twine(signed char Val)
    296       : LHSKind(CharKind), RHSKind(EmptyKind) {
    297       LHS.character = static_cast<char>(Val);
    298     }
    299 
    300     /// Construct from an unsigned char.
    301     explicit Twine(unsigned char Val)
    302       : LHSKind(CharKind), RHSKind(EmptyKind) {
    303       LHS.character = static_cast<char>(Val);
    304     }
    305 
    306     /// Construct a twine to print \p Val as an unsigned decimal integer.
    307     explicit Twine(unsigned Val)
    308       : LHSKind(DecUIKind), RHSKind(EmptyKind) {
    309       LHS.decUI = Val;
    310     }
    311 
    312     /// Construct a twine to print \p Val as a signed decimal integer.
    313     explicit Twine(int Val)
    314       : LHSKind(DecIKind), RHSKind(EmptyKind) {
    315       LHS.decI = Val;
    316     }
    317 
    318     /// Construct a twine to print \p Val as an unsigned decimal integer.
    319     explicit Twine(const unsigned long &Val)
    320       : LHSKind(DecULKind), RHSKind(EmptyKind) {
    321       LHS.decUL = &Val;
    322     }
    323 
    324     /// Construct a twine to print \p Val as a signed decimal integer.
    325     explicit Twine(const long &Val)
    326       : LHSKind(DecLKind), RHSKind(EmptyKind) {
    327       LHS.decL = &Val;
    328     }
    329 
    330     /// Construct a twine to print \p Val as an unsigned decimal integer.
    331     explicit Twine(const unsigned long long &Val)
    332       : LHSKind(DecULLKind), RHSKind(EmptyKind) {
    333       LHS.decULL = &Val;
    334     }
    335 
    336     /// Construct a twine to print \p Val as a signed decimal integer.
    337     explicit Twine(const long long &Val)
    338       : LHSKind(DecLLKind), RHSKind(EmptyKind) {
    339       LHS.decLL = &Val;
    340     }
    341 
    342     // FIXME: Unfortunately, to make sure this is as efficient as possible we
    343     // need extra binary constructors from particular types. We can't rely on
    344     // the compiler to be smart enough to fold operator+()/concat() down to the
    345     // right thing. Yet.
    346 
    347     /// Construct as the concatenation of a C string and a StringRef.
    348     /*implicit*/ Twine(const char *_LHS, const StringRef &_RHS)
    349       : LHSKind(CStringKind), RHSKind(StringRefKind) {
    350       LHS.cString = _LHS;
    351       RHS.stringRef = &_RHS;
    352       assert(isValid() && "Invalid twine!");
    353     }
    354 
    355     /// Construct as the concatenation of a StringRef and a C string.
    356     /*implicit*/ Twine(const StringRef &_LHS, const char *_RHS)
    357       : LHSKind(StringRefKind), RHSKind(CStringKind) {
    358       LHS.stringRef = &_LHS;
    359       RHS.cString = _RHS;
    360       assert(isValid() && "Invalid twine!");
    361     }
    362 
    363     /// Create a 'null' string, which is an empty string that always
    364     /// concatenates to form another empty string.
    365     static Twine createNull() {
    366       return Twine(NullKind);
    367     }
    368 
    369     /// @}
    370     /// @name Numeric Conversions
    371     /// @{
    372 
    373     // Construct a twine to print \p Val as an unsigned hexadecimal integer.
    374     static Twine utohexstr(const uint64_t &Val) {
    375       Child LHS, RHS;
    376       LHS.uHex = &Val;
    377       RHS.twine = 0;
    378       return Twine(LHS, UHexKind, RHS, EmptyKind);
    379     }
    380 
    381     /// @}
    382     /// @name Predicate Operations
    383     /// @{
    384 
    385     /// isTriviallyEmpty - Check if this twine is trivially empty; a false
    386     /// return value does not necessarily mean the twine is empty.
    387     bool isTriviallyEmpty() const {
    388       return isNullary();
    389     }
    390 
    391     /// isSingleStringRef - Return true if this twine can be dynamically
    392     /// accessed as a single StringRef value with getSingleStringRef().
    393     bool isSingleStringRef() const {
    394       if (getRHSKind() != EmptyKind) return false;
    395 
    396       switch (getLHSKind()) {
    397       case EmptyKind:
    398       case CStringKind:
    399       case StdStringKind:
    400       case StringRefKind:
    401         return true;
    402       default:
    403         return false;
    404       }
    405     }
    406 
    407     /// @}
    408     /// @name String Operations
    409     /// @{
    410 
    411     Twine concat(const Twine &Suffix) const;
    412 
    413     /// @}
    414     /// @name Output & Conversion.
    415     /// @{
    416 
    417     /// str - Return the twine contents as a std::string.
    418     std::string str() const;
    419 
    420     /// toVector - Write the concatenated string into the given SmallString or
    421     /// SmallVector.
    422     void toVector(SmallVectorImpl<char> &Out) const;
    423 
    424     /// getSingleStringRef - This returns the twine as a single StringRef.  This
    425     /// method is only valid if isSingleStringRef() is true.
    426     StringRef getSingleStringRef() const {
    427       assert(isSingleStringRef() &&"This cannot be had as a single stringref!");
    428       switch (getLHSKind()) {
    429       default: llvm_unreachable("Out of sync with isSingleStringRef");
    430       case EmptyKind:      return StringRef();
    431       case CStringKind:    return StringRef(LHS.cString);
    432       case StdStringKind:  return StringRef(*LHS.stdString);
    433       case StringRefKind:  return *LHS.stringRef;
    434       }
    435     }
    436 
    437     /// toStringRef - This returns the twine as a single StringRef if it can be
    438     /// represented as such. Otherwise the twine is written into the given
    439     /// SmallVector and a StringRef to the SmallVector's data is returned.
    440     StringRef toStringRef(SmallVectorImpl<char> &Out) const;
    441 
    442     /// toNullTerminatedStringRef - This returns the twine as a single null
    443     /// terminated StringRef if it can be represented as such. Otherwise the
    444     /// twine is written into the given SmallVector and a StringRef to the
    445     /// SmallVector's data is returned.
    446     ///
    447     /// The returned StringRef's size does not include the null terminator.
    448     StringRef toNullTerminatedStringRef(SmallVectorImpl<char> &Out) const;
    449 
    450     /// Write the concatenated string represented by this twine to the
    451     /// stream \p OS.
    452     void print(raw_ostream &OS) const;
    453 
    454     /// Dump the concatenated string represented by this twine to stderr.
    455     void dump() const;
    456 
    457     /// Write the representation of this twine to the stream \p OS.
    458     void printRepr(raw_ostream &OS) const;
    459 
    460     /// Dump the representation of this twine to stderr.
    461     void dumpRepr() const;
    462 
    463     /// @}
    464   };
    465 
    466   /// @name Twine Inline Implementations
    467   /// @{
    468 
    469   inline Twine Twine::concat(const Twine &Suffix) const {
    470     // Concatenation with null is null.
    471     if (isNull() || Suffix.isNull())
    472       return Twine(NullKind);
    473 
    474     // Concatenation with empty yields the other side.
    475     if (isEmpty())
    476       return Suffix;
    477     if (Suffix.isEmpty())
    478       return *this;
    479 
    480     // Otherwise we need to create a new node, taking care to fold in unary
    481     // twines.
    482     Child NewLHS, NewRHS;
    483     NewLHS.twine = this;
    484     NewRHS.twine = &Suffix;
    485     NodeKind NewLHSKind = TwineKind, NewRHSKind = TwineKind;
    486     if (isUnary()) {
    487       NewLHS = LHS;
    488       NewLHSKind = getLHSKind();
    489     }
    490     if (Suffix.isUnary()) {
    491       NewRHS = Suffix.LHS;
    492       NewRHSKind = Suffix.getLHSKind();
    493     }
    494 
    495     return Twine(NewLHS, NewLHSKind, NewRHS, NewRHSKind);
    496   }
    497 
    498   inline Twine operator+(const Twine &LHS, const Twine &RHS) {
    499     return LHS.concat(RHS);
    500   }
    501 
    502   /// Additional overload to guarantee simplified codegen; this is equivalent to
    503   /// concat().
    504 
    505   inline Twine operator+(const char *LHS, const StringRef &RHS) {
    506     return Twine(LHS, RHS);
    507   }
    508 
    509   /// Additional overload to guarantee simplified codegen; this is equivalent to
    510   /// concat().
    511 
    512   inline Twine operator+(const StringRef &LHS, const char *RHS) {
    513     return Twine(LHS, RHS);
    514   }
    515 
    516   inline raw_ostream &operator<<(raw_ostream &OS, const Twine &RHS) {
    517     RHS.print(OS);
    518     return OS;
    519   }
    520 
    521   /// @}
    522 }
    523 
    524 #endif
    525