Coverage Report

Created: 2018-12-14 11:24

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