LLVM API Documentation
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