LLVM API Documentation

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/StringRef.h"
00014 #include "llvm/Support/DataTypes.h"
00015 #include <cassert>
00016 #include <string>
00017 
00018 namespace llvm {
00019   template <typename T>
00020   class SmallVectorImpl;
00021   class StringRef;
00022   class raw_ostream;
00023 
00024   /// Twine - A lightweight data structure for efficiently representing the
00025   /// concatenation of temporary values as strings.
00026   ///
00027   /// A Twine is a kind of rope, it represents a concatenated string using a
00028   /// binary-tree, where the string is the preorder of the nodes. Since the
00029   /// Twine can be efficiently rendered into a buffer when its result is used,
00030   /// it avoids the cost of generating temporary values for intermediate string
00031   /// results -- particularly in cases when the Twine result is never
00032   /// required. By explicitly tracking the type of leaf nodes, we can also avoid
00033   /// the creation of temporary strings for conversions operations (such as
00034   /// appending an integer to a string).
00035   ///
00036   /// A Twine is not intended for use directly and should not be stored, its
00037   /// implementation relies on the ability to store pointers to temporary stack
00038   /// objects which may be deallocated at the end of a statement. Twines should
00039   /// only be used accepted as const references in arguments, when an API wishes
00040   /// to accept possibly-concatenated strings.
00041   ///
00042   /// Twines support a special 'null' value, which always concatenates to form
00043   /// itself, and renders as an empty string. This can be returned from APIs to
00044   /// effectively nullify any concatenations performed on the result.
00045   /// 
00046   /// \b Implementation \n
00047   ///
00048   /// Given the nature of a Twine, it is not possible for the Twine's
00049   /// concatenation method to construct interior nodes; the result must be
00050   /// represented inside the returned value. For this reason a Twine object
00051   /// actually holds two values, the left- and right-hand sides of a
00052   /// concatenation. We also have nullary Twine objects, which are effectively
00053   /// sentinel values that represent empty strings.
00054   ///
00055   /// Thus, a Twine can effectively have zero, one, or two children. The \see
00056   /// isNullary(), \see isUnary(), and \see isBinary() predicates exist for
00057   /// testing the number of children.
00058   ///
00059   /// We maintain a number of invariants on Twine objects (FIXME: Why):
00060   ///  - Nullary twines are always represented with their Kind on the left-hand
00061   ///    side, and the Empty kind on the right-hand side.
00062   ///  - Unary twines are always represented with the value on the left-hand
00063   ///    side, and the Empty kind on the right-hand side.
00064   ///  - If a Twine has another Twine as a child, that child should always be
00065   ///    binary (otherwise it could have been folded into the parent).
00066   ///
00067   /// These invariants are check by \see isValid().
00068   ///
00069   /// \b Efficiency Considerations \n
00070   ///
00071   /// The Twine is designed to yield efficient and small code for common
00072   /// situations. For this reason, the concat() method is inlined so that
00073   /// concatenations of leaf nodes can be optimized into stores directly into a
00074   /// single stack allocated object.
00075   ///
00076   /// In practice, not all compilers can be trusted to optimize concat() fully,
00077   /// so we provide two additional methods (and accompanying operator+
00078   /// overloads) to guarantee that particularly important cases (cstring plus
00079   /// StringRef) codegen as desired.
00080   class Twine {
00081     /// NodeKind - Represent the type of an argument.
00082     enum NodeKind {
00083       /// An empty string; the result of concatenating anything with it is also
00084       /// empty.
00085       NullKind,
00086 
00087       /// The empty string.
00088       EmptyKind,
00089 
00090       /// A pointer to a Twine instance.
00091       TwineKind,
00092 
00093       /// A pointer to a C string instance.
00094       CStringKind,
00095 
00096       /// A pointer to an std::string instance.
00097       StdStringKind,
00098 
00099       /// A pointer to a StringRef instance.
00100       StringRefKind,
00101 
00102       /// A pointer to an unsigned int value, to render as an unsigned decimal
00103       /// integer.
00104       DecUIKind,
00105 
00106       /// A pointer to an int value, to render as a signed decimal integer.
00107       DecIKind,
00108 
00109       /// A pointer to an unsigned long value, to render as an unsigned decimal
00110       /// integer.
00111       DecULKind,
00112 
00113       /// A pointer to a long value, to render as a signed decimal integer.
00114       DecLKind,
00115 
00116       /// A pointer to an unsigned long long value, to render as an unsigned
00117       /// decimal integer.
00118       DecULLKind,
00119 
00120       /// A pointer to a long long value, to render as a signed decimal integer.
00121       DecLLKind,
00122 
00123       /// A pointer to a uint64_t value, to render as an unsigned hexadecimal
00124       /// integer.
00125       UHexKind
00126     };
00127 
00128   private:
00129     /// LHS - The prefix in the concatenation, which may be uninitialized for
00130     /// Null or Empty kinds.
00131     const void *LHS;
00132     /// RHS - The suffix in the concatenation, which may be uninitialized for
00133     /// Null or Empty kinds.
00134     const void *RHS;
00135     /// LHSKind - The NodeKind of the left hand side, \see getLHSKind().
00136     NodeKind LHSKind : 8;
00137     /// RHSKind - The NodeKind of the left hand side, \see getLHSKind().
00138     NodeKind RHSKind : 8;
00139 
00140   private:
00141     /// Construct a nullary twine; the kind must be NullKind or EmptyKind.
00142     explicit Twine(NodeKind Kind)
00143       : LHSKind(Kind), RHSKind(EmptyKind) {
00144       assert(isNullary() && "Invalid kind!");
00145     }
00146 
00147     /// Construct a binary twine.
00148     explicit Twine(const Twine &_LHS, const Twine &_RHS)
00149       : LHS(&_LHS), RHS(&_RHS), LHSKind(TwineKind), RHSKind(TwineKind) {
00150       assert(isValid() && "Invalid twine!");
00151     }
00152 
00153     /// Construct a twine from explicit values.
00154     explicit Twine(const void *_LHS, NodeKind _LHSKind,
00155                    const void *_RHS, NodeKind _RHSKind)
00156       : LHS(_LHS), RHS(_RHS), LHSKind(_LHSKind), RHSKind(_RHSKind) {
00157       assert(isValid() && "Invalid twine!");
00158     }
00159 
00160     /// isNull - Check for the null twine.
00161     bool isNull() const {
00162       return getLHSKind() == NullKind;
00163     }
00164 
00165     /// isEmpty - Check for the empty twine.
00166     bool isEmpty() const {
00167       return getLHSKind() == EmptyKind;
00168     }
00169 
00170     /// isNullary - Check if this is a nullary twine (null or empty).
00171     bool isNullary() const {
00172       return isNull() || isEmpty();
00173     }
00174 
00175     /// isUnary - Check if this is a unary twine.
00176     bool isUnary() const {
00177       return getRHSKind() == EmptyKind && !isNullary();
00178     }
00179 
00180     /// isBinary - Check if this is a binary twine.
00181     bool isBinary() const {
00182       return getLHSKind() != NullKind && getRHSKind() != EmptyKind;
00183     }
00184 
00185     /// isValid - Check if this is a valid twine (satisfying the invariants on
00186     /// order and number of arguments).
00187     bool isValid() const {
00188       // Nullary twines always have Empty on the RHS.
00189       if (isNullary() && getRHSKind() != EmptyKind)
00190         return false;
00191 
00192       // Null should never appear on the RHS.
00193       if (getRHSKind() == NullKind)
00194         return false;
00195 
00196       // The RHS cannot be non-empty if the LHS is empty.
00197       if (getRHSKind() != EmptyKind && getLHSKind() == EmptyKind)
00198         return false;
00199 
00200       // A twine child should always be binary.
00201       if (getLHSKind() == TwineKind &&
00202           !static_cast<const Twine*>(LHS)->isBinary())
00203         return false;
00204       if (getRHSKind() == TwineKind &&
00205           !static_cast<const Twine*>(RHS)->isBinary())
00206         return false;
00207 
00208       return true;
00209     }
00210 
00211     /// getLHSKind - Get the NodeKind of the left-hand side.
00212     NodeKind getLHSKind() const { return LHSKind; }
00213 
00214     /// getRHSKind - Get the NodeKind of the left-hand side.
00215     NodeKind getRHSKind() const { return RHSKind; }
00216 
00217     /// printOneChild - Print one child from a twine.
00218     void printOneChild(raw_ostream &OS, const void *Ptr, NodeKind Kind) const;
00219 
00220     /// printOneChildRepr - Print the representation of one child from a twine.
00221     void printOneChildRepr(raw_ostream &OS, const void *Ptr,
00222                            NodeKind Kind) const;
00223 
00224   public:
00225     /// @name Constructors
00226     /// @{
00227 
00228     /// Construct from an empty string.
00229     /*implicit*/ Twine() : LHSKind(EmptyKind), RHSKind(EmptyKind) {
00230       assert(isValid() && "Invalid twine!");
00231     }
00232 
00233     /// Construct from a C string.
00234     ///
00235     /// We take care here to optimize "" into the empty twine -- this will be
00236     /// optimized out for string constants. This allows Twine arguments have
00237     /// default "" values, without introducing unnecessary string constants.
00238     /*implicit*/ Twine(const char *Str)
00239       : RHSKind(EmptyKind) {
00240       if (Str[0] != '\0') {
00241         LHS = Str;
00242         LHSKind = CStringKind;
00243       } else
00244         LHSKind = EmptyKind;
00245 
00246       assert(isValid() && "Invalid twine!");
00247     }
00248 
00249     /// Construct from an std::string.
00250     /*implicit*/ Twine(const std::string &Str)
00251       : LHS(&Str), LHSKind(StdStringKind), RHSKind(EmptyKind) {
00252       assert(isValid() && "Invalid twine!");
00253     }
00254 
00255     /// Construct from a StringRef.
00256     /*implicit*/ Twine(const StringRef &Str)
00257       : LHS(&Str), LHSKind(StringRefKind), RHSKind(EmptyKind) {
00258       assert(isValid() && "Invalid twine!");
00259     }
00260 
00261     /// Construct a twine to print \arg Val as an unsigned decimal integer.
00262     explicit Twine(const unsigned int &Val) 
00263       : LHS(&Val), LHSKind(DecUIKind), RHSKind(EmptyKind) {
00264     }
00265 
00266     /// Construct a twine to print \arg Val as a signed decimal integer.
00267     explicit Twine(const int &Val) 
00268       : LHS(&Val), LHSKind(DecIKind), RHSKind(EmptyKind) {
00269     }
00270 
00271     /// Construct a twine to print \arg Val as an unsigned decimal integer.
00272     explicit Twine(const unsigned long &Val) 
00273       : LHS(&Val), LHSKind(DecULKind), RHSKind(EmptyKind) {
00274     }
00275 
00276     /// Construct a twine to print \arg Val as a signed decimal integer.
00277     explicit Twine(const long &Val) 
00278       : LHS(&Val), LHSKind(DecLKind), RHSKind(EmptyKind) {
00279     }
00280 
00281     /// Construct a twine to print \arg Val as an unsigned decimal integer.
00282     explicit Twine(const unsigned long long &Val) 
00283       : LHS(&Val), LHSKind(DecULLKind), RHSKind(EmptyKind) {
00284     }
00285 
00286     /// Construct a twine to print \arg Val as a signed decimal integer.
00287     explicit Twine(const long long &Val) 
00288       : LHS(&Val), LHSKind(DecLLKind), RHSKind(EmptyKind) {
00289     }
00290 
00291     // FIXME: Unfortunately, to make sure this is as efficient as possible we
00292     // need extra binary constructors from particular types. We can't rely on
00293     // the compiler to be smart enough to fold operator+()/concat() down to the
00294     // right thing. Yet.
00295 
00296     /// Construct as the concatenation of a C string and a StringRef.
00297     /*implicit*/ Twine(const char *_LHS, const StringRef &_RHS)
00298       : LHS(_LHS), RHS(&_RHS), LHSKind(CStringKind), RHSKind(StringRefKind) {
00299       assert(isValid() && "Invalid twine!");
00300     }
00301 
00302     /// Construct as the concatenation of a StringRef and a C string.
00303     /*implicit*/ Twine(const StringRef &_LHS, const char *_RHS)
00304       : LHS(&_LHS), RHS(_RHS), LHSKind(StringRefKind), RHSKind(CStringKind) {
00305       assert(isValid() && "Invalid twine!");
00306     }
00307 
00308     /// Create a 'null' string, which is an empty string that always
00309     /// concatenates to form another empty string.
00310     static Twine createNull() {
00311       return Twine(NullKind);
00312     }
00313 
00314     /// @}
00315     /// @name Numeric Conversions
00316     /// @{
00317 
00318     // Construct a twine to print \arg Val as an unsigned hexadecimal integer.
00319     static Twine utohexstr(const uint64_t &Val) {
00320       return Twine(&Val, UHexKind, 0, EmptyKind);
00321     }
00322 
00323     /// @}
00324     /// @name Predicate Operations
00325     /// @{
00326 
00327     /// isTriviallyEmpty - Check if this twine is trivially empty; a false
00328     /// return value does not necessarily mean the twine is empty.
00329     bool isTriviallyEmpty() const {
00330       return isNullary();
00331     }
00332 
00333     /// @}
00334     /// @name String Operations
00335     /// @{
00336 
00337     Twine concat(const Twine &Suffix) const;
00338 
00339     /// @}
00340     /// @name Output & Conversion.
00341     /// @{
00342 
00343     /// str - Return the twine contents as a std::string.
00344     std::string str() const;
00345 
00346     /// toVector - Write the concatenated string into the given SmallString or
00347     /// SmallVector.
00348     void toVector(SmallVectorImpl<char> &Out) const;
00349 
00350     /// print - Write the concatenated string represented by this twine to the
00351     /// stream \arg OS.
00352     void print(raw_ostream &OS) const;
00353 
00354     /// dump - Dump the concatenated string represented by this twine to stderr.
00355     void dump() const;
00356 
00357     /// print - Write the representation of this twine to the stream \arg OS.
00358     void printRepr(raw_ostream &OS) const;
00359 
00360     /// dumpRepr - Dump the representation of this twine to stderr.
00361     void dumpRepr() const;
00362 
00363     /// @}
00364   };
00365 
00366   /// @name Twine Inline Implementations
00367   /// @{
00368 
00369   inline Twine Twine::concat(const Twine &Suffix) const {
00370     // Concatenation with null is null.
00371     if (isNull() || Suffix.isNull())
00372       return Twine(NullKind);
00373 
00374     // Concatenation with empty yields the other side.
00375     if (isEmpty())
00376       return Suffix;
00377     if (Suffix.isEmpty())
00378       return *this;
00379 
00380     // Otherwise we need to create a new node, taking care to fold in unary
00381     // twines.
00382     const void *NewLHS = this, *NewRHS = &Suffix;
00383     NodeKind NewLHSKind = TwineKind, NewRHSKind = TwineKind;
00384     if (isUnary()) {
00385       NewLHS = LHS;
00386       NewLHSKind = getLHSKind();
00387     }
00388     if (Suffix.isUnary()) {
00389       NewRHS = Suffix.LHS;
00390       NewRHSKind = Suffix.getLHSKind();
00391     }
00392 
00393     return Twine(NewLHS, NewLHSKind, NewRHS, NewRHSKind);
00394   }
00395 
00396   inline Twine operator+(const Twine &LHS, const Twine &RHS) {
00397     return LHS.concat(RHS);
00398   }
00399 
00400   /// Additional overload to guarantee simplified codegen; this is equivalent to
00401   /// concat().
00402 
00403   inline Twine operator+(const char *LHS, const StringRef &RHS) {
00404     return Twine(LHS, RHS);
00405   }
00406 
00407   /// Additional overload to guarantee simplified codegen; this is equivalent to
00408   /// concat().
00409 
00410   inline Twine operator+(const StringRef &LHS, const char *RHS) {
00411     return Twine(LHS, RHS);
00412   }
00413 
00414   inline raw_ostream &operator<<(raw_ostream &OS, const Twine &RHS) {
00415     RHS.print(OS);
00416     return OS;
00417   }
00418 
00419   /// @}
00420 }
00421 
00422 #endif