include/llvm/ADT/Twine.h

   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.
 163     explicit Twine(NodeKind Kind)
 164       : LHSKind(Kind), RHSKind(EmptyKind) {
 165       assert(isNullary() && "Invalid kind!");
 166     }
 167
 168     /// Construct a binary twine.
 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.
 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.
 187     bool isNull() const {
 188       return getLHSKind() == NullKind;
 189     }
 190
 191     /// Check for the empty twine.
 192     bool isEmpty() const {
 193       return getLHSKind() == EmptyKind;
 194     }
 195
 196     /// Check if this is a nullary twine (null or empty).
 197     bool isNullary() const {
 198       return isNull() || isEmpty();
 199     }
 200
 201     /// Check if this is a unary twine.
 202     bool isUnary() const {
 203       return getRHSKind() == EmptyKind && !isNullary();
 204     }
 205
 206     /// Check if this is a binary twine.
 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).
 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.
 238     NodeKind getLHSKind() const { return LHSKind; }
 239
 240     /// Get the NodeKind of the right-hand side.
 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.
 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.
 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.
 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.
 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.
 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.
 299     explicit Twine(char Val)
 300       : LHSKind(CharKind), RHSKind(EmptyKind) {
 301       LHS.character = Val;
 302     }
 303
 304     /// Construct from a signed char.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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().
 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.
 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.
 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
 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