Coverage Report

Created: 2019-03-24 22:13

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