LLVM  mainline
Twine.h
Go to the documentation of this file.
00001 //===-- Twine.h - Fast Temporary String Concatenation -----------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 
00010 #ifndef LLVM_ADT_TWINE_H
00011 #define LLVM_ADT_TWINE_H
00012 
00013 #include "llvm/ADT/SmallVector.h"
00014 #include "llvm/ADT/StringRef.h"
00015 #include "llvm/Support/DataTypes.h"
00016 #include "llvm/Support/ErrorHandling.h"
00017 #include <cassert>
00018 #include <string>
00019 
00020 namespace llvm {
00021   class raw_ostream;
00022 
00023   /// Twine - A lightweight data structure for efficiently representing the
00024   /// concatenation of temporary values as strings.
00025   ///
00026   /// A Twine is a kind of rope, it represents a concatenated string using a
00027   /// binary-tree, where the string is the preorder of the nodes. Since the
00028   /// Twine can be efficiently rendered into a buffer when its result is used,
00029   /// it avoids the cost of generating temporary values for intermediate string
00030   /// results -- particularly in cases when the Twine result is never
00031   /// required. By explicitly tracking the type of leaf nodes, we can also avoid
00032   /// the creation of temporary strings for conversions operations (such as
00033   /// appending an integer to a string).
00034   ///
00035   /// A Twine is not intended for use directly and should not be stored, its
00036   /// implementation relies on the ability to store pointers to temporary stack
00037   /// objects which may be deallocated at the end of a statement. Twines should
00038   /// only be used accepted as const references in arguments, when an API wishes
00039   /// to accept possibly-concatenated strings.
00040   ///
00041   /// Twines support a special 'null' value, which always concatenates to form
00042   /// itself, and renders as an empty string. This can be returned from APIs to
00043   /// effectively nullify any concatenations performed on the result.
00044   ///
00045   /// \b Implementation
00046   ///
00047   /// Given the nature of a Twine, it is not possible for the Twine's
00048   /// concatenation method to construct interior nodes; the result must be
00049   /// represented inside the returned value. For this reason a Twine object
00050   /// actually holds two values, the left- and right-hand sides of a
00051   /// concatenation. We also have nullary Twine objects, which are effectively
00052   /// sentinel values that represent empty strings.
00053   ///
00054   /// Thus, a Twine can effectively have zero, one, or two children. The \see
00055   /// isNullary(), \see isUnary(), and \see isBinary() predicates exist for
00056   /// testing the number of children.
00057   ///
00058   /// We maintain a number of invariants on Twine objects (FIXME: Why):
00059   ///  - Nullary twines are always represented with their Kind on the left-hand
00060   ///    side, and the Empty kind on the right-hand side.
00061   ///  - Unary twines are always represented with the value on the left-hand
00062   ///    side, and the Empty kind on the right-hand side.
00063   ///  - If a Twine has another Twine as a child, that child should always be
00064   ///    binary (otherwise it could have been folded into the parent).
00065   ///
00066   /// These invariants are check by \see isValid().
00067   ///
00068   /// \b Efficiency Considerations
00069   ///
00070   /// The Twine is designed to yield efficient and small code for common
00071   /// situations. For this reason, the concat() method is inlined so that
00072   /// concatenations of leaf nodes can be optimized into stores directly into a
00073   /// single stack allocated object.
00074   ///
00075   /// In practice, not all compilers can be trusted to optimize concat() fully,
00076   /// so we provide two additional methods (and accompanying operator+
00077   /// overloads) to guarantee that particularly important cases (cstring plus
00078   /// StringRef) codegen as desired.
00079   class Twine {
00080     /// NodeKind - Represent the type of an argument.
00081     enum NodeKind : unsigned char {
00082       /// An empty string; the result of concatenating anything with it is also
00083       /// empty.
00084       NullKind,
00085 
00086       /// The empty string.
00087       EmptyKind,
00088 
00089       /// A pointer to a Twine instance.
00090       TwineKind,
00091 
00092       /// A pointer to a C string instance.
00093       CStringKind,
00094 
00095       /// A pointer to an std::string instance.
00096       StdStringKind,
00097 
00098       /// A pointer to a StringRef instance.
00099       StringRefKind,
00100 
00101       /// A pointer to a SmallString instance.
00102       SmallStringKind,
00103 
00104       /// A char value reinterpreted as a pointer, to render as a character.
00105       CharKind,
00106 
00107       /// An unsigned int value reinterpreted as a pointer, to render as an
00108       /// unsigned decimal integer.
00109       DecUIKind,
00110 
00111       /// An int value reinterpreted as a pointer, to render as a signed
00112       /// decimal integer.
00113       DecIKind,
00114 
00115       /// A pointer to an unsigned long value, to render as an unsigned decimal
00116       /// integer.
00117       DecULKind,
00118 
00119       /// A pointer to a long value, to render as a signed decimal integer.
00120       DecLKind,
00121 
00122       /// A pointer to an unsigned long long value, to render as an unsigned
00123       /// decimal integer.
00124       DecULLKind,
00125 
00126       /// A pointer to a long long value, to render as a signed decimal integer.
00127       DecLLKind,
00128 
00129       /// A pointer to a uint64_t value, to render as an unsigned hexadecimal
00130       /// integer.
00131       UHexKind
00132     };
00133 
00134     union Child
00135     {
00136       const Twine *twine;
00137       const char *cString;
00138       const std::string *stdString;
00139       const StringRef *stringRef;
00140       const SmallVectorImpl<char> *smallString;
00141       char character;
00142       unsigned int decUI;
00143       int decI;
00144       const unsigned long *decUL;
00145       const long *decL;
00146       const unsigned long long *decULL;
00147       const long long *decLL;
00148       const uint64_t *uHex;
00149     };
00150 
00151   private:
00152     /// LHS - The prefix in the concatenation, which may be uninitialized for
00153     /// Null or Empty kinds.
00154     Child LHS;
00155     /// RHS - The suffix in the concatenation, which may be uninitialized for
00156     /// Null or Empty kinds.
00157     Child RHS;
00158     /// LHSKind - The NodeKind of the left hand side, \see getLHSKind().
00159     NodeKind LHSKind;
00160     /// RHSKind - The NodeKind of the right hand side, \see getRHSKind().
00161     NodeKind RHSKind;
00162 
00163   private:
00164     /// Construct a nullary twine; the kind must be NullKind or EmptyKind.
00165     explicit Twine(NodeKind Kind)
00166       : LHSKind(Kind), RHSKind(EmptyKind) {
00167       assert(isNullary() && "Invalid kind!");
00168     }
00169 
00170     /// Construct a binary twine.
00171     explicit Twine(const Twine &LHS, const Twine &RHS)
00172         : LHSKind(TwineKind), RHSKind(TwineKind) {
00173       this->LHS.twine = &LHS;
00174       this->RHS.twine = &RHS;
00175       assert(isValid() && "Invalid twine!");
00176     }
00177 
00178     /// Construct a twine from explicit values.
00179     explicit Twine(Child LHS, NodeKind LHSKind, Child RHS, NodeKind RHSKind)
00180         : LHS(LHS), RHS(RHS), LHSKind(LHSKind), RHSKind(RHSKind) {
00181       assert(isValid() && "Invalid twine!");
00182     }
00183 
00184     /// Since the intended use of twines is as temporary objects, assignments
00185     /// when concatenating might cause undefined behavior or stack corruptions
00186     Twine &operator=(const Twine &Other) = delete;
00187 
00188     /// Check for the null twine.
00189     bool isNull() const {
00190       return getLHSKind() == NullKind;
00191     }
00192 
00193     /// Check for the empty twine.
00194     bool isEmpty() const {
00195       return getLHSKind() == EmptyKind;
00196     }
00197 
00198     /// Check if this is a nullary twine (null or empty).
00199     bool isNullary() const {
00200       return isNull() || isEmpty();
00201     }
00202 
00203     /// Check if this is a unary twine.
00204     bool isUnary() const {
00205       return getRHSKind() == EmptyKind && !isNullary();
00206     }
00207 
00208     /// Check if this is a binary twine.
00209     bool isBinary() const {
00210       return getLHSKind() != NullKind && getRHSKind() != EmptyKind;
00211     }
00212 
00213     /// Check if this is a valid twine (satisfying the invariants on
00214     /// order and number of arguments).
00215     bool isValid() const {
00216       // Nullary twines always have Empty on the RHS.
00217       if (isNullary() && getRHSKind() != EmptyKind)
00218         return false;
00219 
00220       // Null should never appear on the RHS.
00221       if (getRHSKind() == NullKind)
00222         return false;
00223 
00224       // The RHS cannot be non-empty if the LHS is empty.
00225       if (getRHSKind() != EmptyKind && getLHSKind() == EmptyKind)
00226         return false;
00227 
00228       // A twine child should always be binary.
00229       if (getLHSKind() == TwineKind &&
00230           !LHS.twine->isBinary())
00231         return false;
00232       if (getRHSKind() == TwineKind &&
00233           !RHS.twine->isBinary())
00234         return false;
00235 
00236       return true;
00237     }
00238 
00239     /// Get the NodeKind of the left-hand side.
00240     NodeKind getLHSKind() const { return LHSKind; }
00241 
00242     /// Get the NodeKind of the right-hand side.
00243     NodeKind getRHSKind() const { return RHSKind; }
00244 
00245     /// Print one child from a twine.
00246     void printOneChild(raw_ostream &OS, Child Ptr, NodeKind Kind) const;
00247 
00248     /// Print the representation of one child from a twine.
00249     void printOneChildRepr(raw_ostream &OS, Child Ptr,
00250                            NodeKind Kind) const;
00251 
00252   public:
00253     /// @name Constructors
00254     /// @{
00255 
00256     /// Construct from an empty string.
00257     /*implicit*/ Twine() : LHSKind(EmptyKind), RHSKind(EmptyKind) {
00258       assert(isValid() && "Invalid twine!");
00259     }
00260 
00261     Twine(const Twine &) = default;
00262 
00263     /// Construct from a C string.
00264     ///
00265     /// We take care here to optimize "" into the empty twine -- this will be
00266     /// optimized out for string constants. This allows Twine arguments have
00267     /// default "" values, without introducing unnecessary string constants.
00268     /*implicit*/ Twine(const char *Str)
00269       : RHSKind(EmptyKind) {
00270       if (Str[0] != '\0') {
00271         LHS.cString = Str;
00272         LHSKind = CStringKind;
00273       } else
00274         LHSKind = EmptyKind;
00275 
00276       assert(isValid() && "Invalid twine!");
00277     }
00278 
00279     /// Construct from an std::string.
00280     /*implicit*/ Twine(const std::string &Str)
00281       : LHSKind(StdStringKind), RHSKind(EmptyKind) {
00282       LHS.stdString = &Str;
00283       assert(isValid() && "Invalid twine!");
00284     }
00285 
00286     /// Construct from a StringRef.
00287     /*implicit*/ Twine(const StringRef &Str)
00288       : LHSKind(StringRefKind), RHSKind(EmptyKind) {
00289       LHS.stringRef = &Str;
00290       assert(isValid() && "Invalid twine!");
00291     }
00292 
00293     /// Construct from a SmallString.
00294     /*implicit*/ Twine(const SmallVectorImpl<char> &Str)
00295       : LHSKind(SmallStringKind), RHSKind(EmptyKind) {
00296       LHS.smallString = &Str;
00297       assert(isValid() && "Invalid twine!");
00298     }
00299 
00300     /// Construct from a char.
00301     explicit Twine(char Val)
00302       : LHSKind(CharKind), RHSKind(EmptyKind) {
00303       LHS.character = Val;
00304     }
00305 
00306     /// Construct from a signed char.
00307     explicit Twine(signed char Val)
00308       : LHSKind(CharKind), RHSKind(EmptyKind) {
00309       LHS.character = static_cast<char>(Val);
00310     }
00311 
00312     /// Construct from an unsigned char.
00313     explicit Twine(unsigned char Val)
00314       : LHSKind(CharKind), RHSKind(EmptyKind) {
00315       LHS.character = static_cast<char>(Val);
00316     }
00317 
00318     /// Construct a twine to print \p Val as an unsigned decimal integer.
00319     explicit Twine(unsigned Val)
00320       : LHSKind(DecUIKind), RHSKind(EmptyKind) {
00321       LHS.decUI = Val;
00322     }
00323 
00324     /// Construct a twine to print \p Val as a signed decimal integer.
00325     explicit Twine(int Val)
00326       : LHSKind(DecIKind), RHSKind(EmptyKind) {
00327       LHS.decI = Val;
00328     }
00329 
00330     /// Construct a twine to print \p Val as an unsigned decimal integer.
00331     explicit Twine(const unsigned long &Val)
00332       : LHSKind(DecULKind), RHSKind(EmptyKind) {
00333       LHS.decUL = &Val;
00334     }
00335 
00336     /// Construct a twine to print \p Val as a signed decimal integer.
00337     explicit Twine(const long &Val)
00338       : LHSKind(DecLKind), RHSKind(EmptyKind) {
00339       LHS.decL = &Val;
00340     }
00341 
00342     /// Construct a twine to print \p Val as an unsigned decimal integer.
00343     explicit Twine(const unsigned long long &Val)
00344       : LHSKind(DecULLKind), RHSKind(EmptyKind) {
00345       LHS.decULL = &Val;
00346     }
00347 
00348     /// Construct a twine to print \p Val as a signed decimal integer.
00349     explicit Twine(const long long &Val)
00350       : LHSKind(DecLLKind), RHSKind(EmptyKind) {
00351       LHS.decLL = &Val;
00352     }
00353 
00354     // FIXME: Unfortunately, to make sure this is as efficient as possible we
00355     // need extra binary constructors from particular types. We can't rely on
00356     // the compiler to be smart enough to fold operator+()/concat() down to the
00357     // right thing. Yet.
00358 
00359     /// Construct as the concatenation of a C string and a StringRef.
00360     /*implicit*/ Twine(const char *LHS, const StringRef &RHS)
00361         : LHSKind(CStringKind), RHSKind(StringRefKind) {
00362       this->LHS.cString = LHS;
00363       this->RHS.stringRef = &RHS;
00364       assert(isValid() && "Invalid twine!");
00365     }
00366 
00367     /// Construct as the concatenation of a StringRef and a C string.
00368     /*implicit*/ Twine(const StringRef &LHS, const char *RHS)
00369         : LHSKind(StringRefKind), RHSKind(CStringKind) {
00370       this->LHS.stringRef = &LHS;
00371       this->RHS.cString = RHS;
00372       assert(isValid() && "Invalid twine!");
00373     }
00374 
00375     /// Create a 'null' string, which is an empty string that always
00376     /// concatenates to form another empty string.
00377     static Twine createNull() {
00378       return Twine(NullKind);
00379     }
00380 
00381     /// @}
00382     /// @name Numeric Conversions
00383     /// @{
00384 
00385     // Construct a twine to print \p Val as an unsigned hexadecimal integer.
00386     static Twine utohexstr(const uint64_t &Val) {
00387       Child LHS, RHS;
00388       LHS.uHex = &Val;
00389       RHS.twine = nullptr;
00390       return Twine(LHS, UHexKind, RHS, EmptyKind);
00391     }
00392 
00393     /// @}
00394     /// @name Predicate Operations
00395     /// @{
00396 
00397     /// Check if this twine is trivially empty; a false return value does not
00398     /// necessarily mean the twine is empty.
00399     bool isTriviallyEmpty() const {
00400       return isNullary();
00401     }
00402 
00403     /// Return true if this twine can be dynamically accessed as a single
00404     /// StringRef value with getSingleStringRef().
00405     bool isSingleStringRef() const {
00406       if (getRHSKind() != EmptyKind) return false;
00407 
00408       switch (getLHSKind()) {
00409       case EmptyKind:
00410       case CStringKind:
00411       case StdStringKind:
00412       case StringRefKind:
00413       case SmallStringKind:
00414         return true;
00415       default:
00416         return false;
00417       }
00418     }
00419 
00420     /// @}
00421     /// @name String Operations
00422     /// @{
00423 
00424     Twine concat(const Twine &Suffix) const;
00425 
00426     /// @}
00427     /// @name Output & Conversion.
00428     /// @{
00429 
00430     /// Return the twine contents as a std::string.
00431     std::string str() const;
00432 
00433     /// Append the concatenated string into the given SmallString or SmallVector.
00434     void toVector(SmallVectorImpl<char> &Out) const;
00435 
00436     /// This returns the twine as a single StringRef.  This method is only valid
00437     /// if isSingleStringRef() is true.
00438     StringRef getSingleStringRef() const {
00439       assert(isSingleStringRef() &&"This cannot be had as a single stringref!");
00440       switch (getLHSKind()) {
00441       default: llvm_unreachable("Out of sync with isSingleStringRef");
00442       case EmptyKind:      return StringRef();
00443       case CStringKind:    return StringRef(LHS.cString);
00444       case StdStringKind:  return StringRef(*LHS.stdString);
00445       case StringRefKind:  return *LHS.stringRef;
00446       case SmallStringKind:
00447         return StringRef(LHS.smallString->data(), LHS.smallString->size());
00448       }
00449     }
00450 
00451     /// This returns the twine as a single StringRef if it can be
00452     /// represented as such. Otherwise the twine is written into the given
00453     /// SmallVector and a StringRef to the SmallVector's data is returned.
00454     StringRef toStringRef(SmallVectorImpl<char> &Out) const {
00455       if (isSingleStringRef())
00456         return getSingleStringRef();
00457       toVector(Out);
00458       return StringRef(Out.data(), Out.size());
00459     }
00460 
00461     /// This returns the twine as a single null terminated StringRef if it
00462     /// can be represented as such. Otherwise the twine is written into the
00463     /// given SmallVector and a StringRef to the SmallVector's data is returned.
00464     ///
00465     /// The returned StringRef's size does not include the null terminator.
00466     StringRef toNullTerminatedStringRef(SmallVectorImpl<char> &Out) const;
00467 
00468     /// Write the concatenated string represented by this twine to the
00469     /// stream \p OS.
00470     void print(raw_ostream &OS) const;
00471 
00472     /// Dump the concatenated string represented by this twine to stderr.
00473     void dump() const;
00474 
00475     /// Write the representation of this twine to the stream \p OS.
00476     void printRepr(raw_ostream &OS) const;
00477 
00478     /// Dump the representation of this twine to stderr.
00479     void dumpRepr() const;
00480 
00481     /// @}
00482   };
00483 
00484   /// @name Twine Inline Implementations
00485   /// @{
00486 
00487   inline Twine Twine::concat(const Twine &Suffix) const {
00488     // Concatenation with null is null.
00489     if (isNull() || Suffix.isNull())
00490       return Twine(NullKind);
00491 
00492     // Concatenation with empty yields the other side.
00493     if (isEmpty())
00494       return Suffix;
00495     if (Suffix.isEmpty())
00496       return *this;
00497 
00498     // Otherwise we need to create a new node, taking care to fold in unary
00499     // twines.
00500     Child NewLHS, NewRHS;
00501     NewLHS.twine = this;
00502     NewRHS.twine = &Suffix;
00503     NodeKind NewLHSKind = TwineKind, NewRHSKind = TwineKind;
00504     if (isUnary()) {
00505       NewLHS = LHS;
00506       NewLHSKind = getLHSKind();
00507     }
00508     if (Suffix.isUnary()) {
00509       NewRHS = Suffix.LHS;
00510       NewRHSKind = Suffix.getLHSKind();
00511     }
00512 
00513     return Twine(NewLHS, NewLHSKind, NewRHS, NewRHSKind);
00514   }
00515 
00516   inline Twine operator+(const Twine &LHS, const Twine &RHS) {
00517     return LHS.concat(RHS);
00518   }
00519 
00520   /// Additional overload to guarantee simplified codegen; this is equivalent to
00521   /// concat().
00522 
00523   inline Twine operator+(const char *LHS, const StringRef &RHS) {
00524     return Twine(LHS, RHS);
00525   }
00526 
00527   /// Additional overload to guarantee simplified codegen; this is equivalent to
00528   /// concat().
00529 
00530   inline Twine operator+(const StringRef &LHS, const char *RHS) {
00531     return Twine(LHS, RHS);
00532   }
00533 
00534   inline raw_ostream &operator<<(raw_ostream &OS, const Twine &RHS) {
00535     RHS.print(OS);
00536     return OS;
00537   }
00538 
00539   /// @}
00540 }
00541 
00542 #endif