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/SmallVector.h" 14 #include "llvm/ADT/StringRef.h" 15 #include "llvm/Support/DataTypes.h" 16 #include "llvm/Support/ErrorHandling.h" 17 #include <cassert> 18 #include <string> 19 20 namespace llvm { 21 class raw_ostream; 22 23 /// Twine - A lightweight data structure for efficiently representing the 24 /// concatenation of temporary values as strings. 25 /// 26 /// A Twine is a kind of rope, it represents a concatenated string using a 27 /// binary-tree, where the string is the preorder of the nodes. Since the 28 /// Twine can be efficiently rendered into a buffer when its result is used, 29 /// it avoids the cost of generating temporary values for intermediate string 30 /// results -- particularly in cases when the Twine result is never 31 /// required. By explicitly tracking the type of leaf nodes, we can also avoid 32 /// the creation of temporary strings for conversions operations (such as 33 /// appending an integer to a string). 34 /// 35 /// A Twine is not intended for use directly and should not be stored, its 36 /// implementation relies on the ability to store pointers to temporary stack 37 /// objects which may be deallocated at the end of a statement. Twines should 38 /// only be used accepted as const references in arguments, when an API wishes 39 /// to accept possibly-concatenated strings. 40 /// 41 /// Twines support a special 'null' value, which always concatenates to form 42 /// itself, and renders as an empty string. This can be returned from APIs to 43 /// effectively nullify any concatenations performed on the result. 44 /// 45 /// \b Implementation 46 /// 47 /// Given the nature of a Twine, it is not possible for the Twine's 48 /// concatenation method to construct interior nodes; the result must be 49 /// represented inside the returned value. For this reason a Twine object 50 /// actually holds two values, the left- and right-hand sides of a 51 /// concatenation. We also have nullary Twine objects, which are effectively 52 /// sentinel values that represent empty strings. 53 /// 54 /// Thus, a Twine can effectively have zero, one, or two children. The \see 55 /// isNullary(), \see isUnary(), and \see isBinary() predicates exist for 56 /// testing the number of children. 57 /// 58 /// We maintain a number of invariants on Twine objects (FIXME: Why): 59 /// - Nullary twines are always represented with their Kind on the left-hand 60 /// side, and the Empty kind on the right-hand side. 61 /// - Unary twines are always represented with the value on the left-hand 62 /// side, and the Empty kind on the right-hand side. 63 /// - If a Twine has another Twine as a child, that child should always be 64 /// binary (otherwise it could have been folded into the parent). 65 /// 66 /// These invariants are check by \see isValid(). 67 /// 68 /// \b Efficiency Considerations 69 /// 70 /// The Twine is designed to yield efficient and small code for common 71 /// situations. For this reason, the concat() method is inlined so that 72 /// concatenations of leaf nodes can be optimized into stores directly into a 73 /// single stack allocated object. 74 /// 75 /// In practice, not all compilers can be trusted to optimize concat() fully, 76 /// so we provide two additional methods (and accompanying operator+ 77 /// overloads) to guarantee that particularly important cases (cstring plus 78 /// StringRef) codegen as desired. 79 class Twine { 80 /// NodeKind - Represent the type of an argument. 81 enum NodeKind : unsigned char { 82 /// An empty string; the result of concatenating anything with it is also 83 /// empty. 84 NullKind, 85 86 /// The empty string. 87 EmptyKind, 88 89 /// A pointer to a Twine instance. 90 TwineKind, 91 92 /// A pointer to a C string instance. 93 CStringKind, 94 95 /// A pointer to an std::string instance. 96 StdStringKind, 97 98 /// A pointer to a StringRef instance. 99 StringRefKind, 100 101 /// A pointer to a SmallString instance. 102 SmallStringKind, 103 104 /// A char value, to render as a character. 105 CharKind, 106 107 /// An unsigned int value, to render as an unsigned decimal integer. 108 DecUIKind, 109 110 /// An int value, to render as a signed decimal integer. 111 DecIKind, 112 113 /// A pointer to an unsigned long value, to render as an unsigned decimal 114 /// integer. 115 DecULKind, 116 117 /// A pointer to a long value, to render as a signed decimal integer. 118 DecLKind, 119 120 /// A pointer to an unsigned long long value, to render as an unsigned 121 /// decimal integer. 122 DecULLKind, 123 124 /// A pointer to a long long value, to render as a signed decimal integer. 125 DecLLKind, 126 127 /// A pointer to a uint64_t value, to render as an unsigned hexadecimal 128 /// integer. 129 UHexKind 130 }; 131 132 union Child 133 { 134 const Twine *twine; 135 const char *cString; 136 const std::string *stdString; 137 const StringRef *stringRef; 138 const SmallVectorImpl<char> *smallString; 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 /// LHSKind - The NodeKind of the left hand side, \see getLHSKind(). 157 NodeKind LHSKind; 158 /// RHSKind - The NodeKind of the right hand side, \see getRHSKind(). 159 NodeKind RHSKind; 160 161 private: 162 /// Construct a nullary twine; the kind must be NullKind or EmptyKind. Twine(NodeKind Kind)163 explicit Twine(NodeKind Kind) 164 : LHSKind(Kind), RHSKind(EmptyKind) { 165 assert(isNullary() && "Invalid kind!"); 166 } 167 168 /// Construct a binary twine. Twine(const Twine & LHS,const Twine & RHS)169 explicit Twine(const Twine &LHS, const Twine &RHS) 170 : LHSKind(TwineKind), RHSKind(TwineKind) { 171 this->LHS.twine = &LHS; 172 this->RHS.twine = &RHS; 173 assert(isValid() && "Invalid twine!"); 174 } 175 176 /// Construct a twine from explicit values. Twine(Child LHS,NodeKind LHSKind,Child RHS,NodeKind RHSKind)177 explicit Twine(Child LHS, NodeKind LHSKind, Child RHS, NodeKind RHSKind) 178 : LHS(LHS), RHS(RHS), LHSKind(LHSKind), RHSKind(RHSKind) { 179 assert(isValid() && "Invalid twine!"); 180 } 181 182 /// Since the intended use of twines is as temporary objects, assignments 183 /// when concatenating might cause undefined behavior or stack corruptions 184 Twine &operator=(const Twine &Other) = delete; 185 186 /// Check for the null twine. isNull()187 bool isNull() const { 188 return getLHSKind() == NullKind; 189 } 190 191 /// Check for the empty twine. isEmpty()192 bool isEmpty() const { 193 return getLHSKind() == EmptyKind; 194 } 195 196 /// Check if this is a nullary twine (null or empty). isNullary()197 bool isNullary() const { 198 return isNull() || isEmpty(); 199 } 200 201 /// Check if this is a unary twine. isUnary()202 bool isUnary() const { 203 return getRHSKind() == EmptyKind && !isNullary(); 204 } 205 206 /// Check if this is a binary twine. isBinary()207 bool isBinary() const { 208 return getLHSKind() != NullKind && getRHSKind() != EmptyKind; 209 } 210 211 /// Check if this is a valid twine (satisfying the invariants on 212 /// order and number of arguments). isValid()213 bool isValid() const { 214 // Nullary twines always have Empty on the RHS. 215 if (isNullary() && getRHSKind() != EmptyKind) 216 return false; 217 218 // Null should never appear on the RHS. 219 if (getRHSKind() == NullKind) 220 return false; 221 222 // The RHS cannot be non-empty if the LHS is empty. 223 if (getRHSKind() != EmptyKind && getLHSKind() == EmptyKind) 224 return false; 225 226 // A twine child should always be binary. 227 if (getLHSKind() == TwineKind && 228 !LHS.twine->isBinary()) 229 return false; 230 if (getRHSKind() == TwineKind && 231 !RHS.twine->isBinary()) 232 return false; 233 234 return true; 235 } 236 237 /// Get the NodeKind of the left-hand side. getLHSKind()238 NodeKind getLHSKind() const { return LHSKind; } 239 240 /// Get the NodeKind of the right-hand side. getRHSKind()241 NodeKind getRHSKind() const { return RHSKind; } 242 243 /// Print one child from a twine. 244 void printOneChild(raw_ostream &OS, Child Ptr, NodeKind Kind) const; 245 246 /// Print the representation of one child from a twine. 247 void printOneChildRepr(raw_ostream &OS, Child Ptr, 248 NodeKind Kind) const; 249 250 public: 251 /// @name Constructors 252 /// @{ 253 254 /// Construct from an empty string. Twine()255 /*implicit*/ Twine() : LHSKind(EmptyKind), RHSKind(EmptyKind) { 256 assert(isValid() && "Invalid twine!"); 257 } 258 259 Twine(const Twine &) = default; 260 261 /// Construct from a C string. 262 /// 263 /// We take care here to optimize "" into the empty twine -- this will be 264 /// optimized out for string constants. This allows Twine arguments have 265 /// default "" values, without introducing unnecessary string constants. Twine(const char * Str)266 /*implicit*/ Twine(const char *Str) 267 : RHSKind(EmptyKind) { 268 if (Str[0] != '\0') { 269 LHS.cString = Str; 270 LHSKind = CStringKind; 271 } else 272 LHSKind = EmptyKind; 273 274 assert(isValid() && "Invalid twine!"); 275 } 276 277 /// Construct from an std::string. Twine(const std::string & Str)278 /*implicit*/ Twine(const std::string &Str) 279 : LHSKind(StdStringKind), RHSKind(EmptyKind) { 280 LHS.stdString = &Str; 281 assert(isValid() && "Invalid twine!"); 282 } 283 284 /// Construct from a StringRef. Twine(const StringRef & Str)285 /*implicit*/ Twine(const StringRef &Str) 286 : LHSKind(StringRefKind), RHSKind(EmptyKind) { 287 LHS.stringRef = &Str; 288 assert(isValid() && "Invalid twine!"); 289 } 290 291 /// Construct from a SmallString. Twine(const SmallVectorImpl<char> & Str)292 /*implicit*/ Twine(const SmallVectorImpl<char> &Str) 293 : LHSKind(SmallStringKind), RHSKind(EmptyKind) { 294 LHS.smallString = &Str; 295 assert(isValid() && "Invalid twine!"); 296 } 297 298 /// Construct from a char. Twine(char Val)299 explicit Twine(char Val) 300 : LHSKind(CharKind), RHSKind(EmptyKind) { 301 LHS.character = Val; 302 } 303 304 /// Construct from a signed char. Twine(signed char Val)305 explicit Twine(signed char Val) 306 : LHSKind(CharKind), RHSKind(EmptyKind) { 307 LHS.character = static_cast<char>(Val); 308 } 309 310 /// Construct from an unsigned char. Twine(unsigned char Val)311 explicit Twine(unsigned char Val) 312 : LHSKind(CharKind), RHSKind(EmptyKind) { 313 LHS.character = static_cast<char>(Val); 314 } 315 316 /// Construct a twine to print \p Val as an unsigned decimal integer. Twine(unsigned Val)317 explicit Twine(unsigned Val) 318 : LHSKind(DecUIKind), RHSKind(EmptyKind) { 319 LHS.decUI = Val; 320 } 321 322 /// Construct a twine to print \p Val as a signed decimal integer. Twine(int Val)323 explicit Twine(int Val) 324 : LHSKind(DecIKind), RHSKind(EmptyKind) { 325 LHS.decI = Val; 326 } 327 328 /// Construct a twine to print \p Val as an unsigned decimal integer. Twine(const unsigned long & Val)329 explicit Twine(const unsigned long &Val) 330 : LHSKind(DecULKind), RHSKind(EmptyKind) { 331 LHS.decUL = &Val; 332 } 333 334 /// Construct a twine to print \p Val as a signed decimal integer. Twine(const long & Val)335 explicit Twine(const long &Val) 336 : LHSKind(DecLKind), RHSKind(EmptyKind) { 337 LHS.decL = &Val; 338 } 339 340 /// Construct a twine to print \p Val as an unsigned decimal integer. Twine(const unsigned long long & Val)341 explicit Twine(const unsigned long long &Val) 342 : LHSKind(DecULLKind), RHSKind(EmptyKind) { 343 LHS.decULL = &Val; 344 } 345 346 /// Construct a twine to print \p Val as a signed decimal integer. Twine(const long long & Val)347 explicit Twine(const long long &Val) 348 : LHSKind(DecLLKind), RHSKind(EmptyKind) { 349 LHS.decLL = &Val; 350 } 351 352 // FIXME: Unfortunately, to make sure this is as efficient as possible we 353 // need extra binary constructors from particular types. We can't rely on 354 // the compiler to be smart enough to fold operator+()/concat() down to the 355 // right thing. Yet. 356 357 /// Construct as the concatenation of a C string and a StringRef. Twine(const char * LHS,const StringRef & RHS)358 /*implicit*/ Twine(const char *LHS, const StringRef &RHS) 359 : LHSKind(CStringKind), RHSKind(StringRefKind) { 360 this->LHS.cString = LHS; 361 this->RHS.stringRef = &RHS; 362 assert(isValid() && "Invalid twine!"); 363 } 364 365 /// Construct as the concatenation of a StringRef and a C string. Twine(const StringRef & LHS,const char * RHS)366 /*implicit*/ Twine(const StringRef &LHS, const char *RHS) 367 : LHSKind(StringRefKind), RHSKind(CStringKind) { 368 this->LHS.stringRef = &LHS; 369 this->RHS.cString = RHS; 370 assert(isValid() && "Invalid twine!"); 371 } 372 373 /// Create a 'null' string, which is an empty string that always 374 /// concatenates to form another empty string. createNull()375 static Twine createNull() { 376 return Twine(NullKind); 377 } 378 379 /// @} 380 /// @name Numeric Conversions 381 /// @{ 382 383 // Construct a twine to print \p Val as an unsigned hexadecimal integer. utohexstr(const uint64_t & Val)384 static Twine utohexstr(const uint64_t &Val) { 385 Child LHS, RHS; 386 LHS.uHex = &Val; 387 RHS.twine = nullptr; 388 return Twine(LHS, UHexKind, RHS, EmptyKind); 389 } 390 391 /// @} 392 /// @name Predicate Operations 393 /// @{ 394 395 /// Check if this twine is trivially empty; a false return value does not 396 /// necessarily mean the twine is empty. isTriviallyEmpty()397 bool isTriviallyEmpty() const { 398 return isNullary(); 399 } 400 401 /// Return true if this twine can be dynamically accessed as a single 402 /// StringRef value with getSingleStringRef(). isSingleStringRef()403 bool isSingleStringRef() const { 404 if (getRHSKind() != EmptyKind) return false; 405 406 switch (getLHSKind()) { 407 case EmptyKind: 408 case CStringKind: 409 case StdStringKind: 410 case StringRefKind: 411 case SmallStringKind: 412 return true; 413 default: 414 return false; 415 } 416 } 417 418 /// @} 419 /// @name String Operations 420 /// @{ 421 422 Twine concat(const Twine &Suffix) const; 423 424 /// @} 425 /// @name Output & Conversion. 426 /// @{ 427 428 /// Return the twine contents as a std::string. 429 std::string str() const; 430 431 /// Append the concatenated string into the given SmallString or SmallVector. 432 void toVector(SmallVectorImpl<char> &Out) const; 433 434 /// This returns the twine as a single StringRef. This method is only valid 435 /// if isSingleStringRef() is true. getSingleStringRef()436 StringRef getSingleStringRef() const { 437 assert(isSingleStringRef() &&"This cannot be had as a single stringref!"); 438 switch (getLHSKind()) { 439 default: llvm_unreachable("Out of sync with isSingleStringRef"); 440 case EmptyKind: return StringRef(); 441 case CStringKind: return StringRef(LHS.cString); 442 case StdStringKind: return StringRef(*LHS.stdString); 443 case StringRefKind: return *LHS.stringRef; 444 case SmallStringKind: 445 return StringRef(LHS.smallString->data(), LHS.smallString->size()); 446 } 447 } 448 449 /// This returns the twine as a single StringRef if it can be 450 /// represented as such. Otherwise the twine is written into the given 451 /// SmallVector and a StringRef to the SmallVector's data is returned. toStringRef(SmallVectorImpl<char> & Out)452 StringRef toStringRef(SmallVectorImpl<char> &Out) const { 453 if (isSingleStringRef()) 454 return getSingleStringRef(); 455 toVector(Out); 456 return StringRef(Out.data(), Out.size()); 457 } 458 459 /// This returns the twine as a single null terminated StringRef if it 460 /// can be represented as such. Otherwise the twine is written into the 461 /// given SmallVector and a StringRef to the SmallVector's data is returned. 462 /// 463 /// The returned StringRef's size does not include the null terminator. 464 StringRef toNullTerminatedStringRef(SmallVectorImpl<char> &Out) const; 465 466 /// Write the concatenated string represented by this twine to the 467 /// stream \p OS. 468 void print(raw_ostream &OS) const; 469 470 /// Dump the concatenated string represented by this twine to stderr. 471 void dump() const; 472 473 /// Write the representation of this twine to the stream \p OS. 474 void printRepr(raw_ostream &OS) const; 475 476 /// Dump the representation of this twine to stderr. 477 void dumpRepr() const; 478 479 /// @} 480 }; 481 482 /// @name Twine Inline Implementations 483 /// @{ 484 concat(const Twine & Suffix)485 inline Twine Twine::concat(const Twine &Suffix) const { 486 // Concatenation with null is null. 487 if (isNull() || Suffix.isNull()) 488 return Twine(NullKind); 489 490 // Concatenation with empty yields the other side. 491 if (isEmpty()) 492 return Suffix; 493 if (Suffix.isEmpty()) 494 return *this; 495 496 // Otherwise we need to create a new node, taking care to fold in unary 497 // twines. 498 Child NewLHS, NewRHS; 499 NewLHS.twine = this; 500 NewRHS.twine = &Suffix; 501 NodeKind NewLHSKind = TwineKind, NewRHSKind = TwineKind; 502 if (isUnary()) { 503 NewLHS = LHS; 504 NewLHSKind = getLHSKind(); 505 } 506 if (Suffix.isUnary()) { 507 NewRHS = Suffix.LHS; 508 NewRHSKind = Suffix.getLHSKind(); 509 } 510 511 return Twine(NewLHS, NewLHSKind, NewRHS, NewRHSKind); 512 } 513 514 inline Twine operator+(const Twine &LHS, const Twine &RHS) { 515 return LHS.concat(RHS); 516 } 517 518 /// Additional overload to guarantee simplified codegen; this is equivalent to 519 /// concat(). 520 521 inline Twine operator+(const char *LHS, const StringRef &RHS) { 522 return Twine(LHS, RHS); 523 } 524 525 /// Additional overload to guarantee simplified codegen; this is equivalent to 526 /// concat(). 527 528 inline Twine operator+(const StringRef &LHS, const char *RHS) { 529 return Twine(LHS, RHS); 530 } 531 532 inline raw_ostream &operator<<(raw_ostream &OS, const Twine &RHS) { 533 RHS.print(OS); 534 return OS; 535 } 536 537 /// @} 538 } 539 540 #endif 541