mycpp

Coverage Report

Created: 2024-06-09 06:28

/home/uke/oil/mycpp/gc_str.cc
Line
Count
Source (jump to first uncovered line)
1
#include "mycpp/gc_str.h"
2
3
#include <ctype.h>  // isalpha(), isdigit()
4
#include <stdarg.h>
5
6
#include <regex>
7
8
#include "mycpp/common.h"
9
#include "mycpp/gc_alloc.h"     // NewStr()
10
#include "mycpp/gc_builtins.h"  // StringToInt()
11
#include "mycpp/gc_list.h"      // join(), split() use it
12
13
GLOBAL_STR(kEmptyString, "");
14
15
static const std::regex gStrFmtRegex("([^%]*)(?:%(-?[0-9]*)(.))?");
16
static const int kMaxFmtWidth = 256;  // arbitrary...
17
18
17
int BigStr::find(BigStr* needle, int start, int end) {
19
17
  if (end == -1) {
20
12
    end = len(this);
21
12
  }
22
17
  int needle_len = len(needle);
23
24
17
  if (needle_len > (end - start)) {
25
2
    return -1;  // needle is too long to be found (Python behavior)
26
2
  }
27
28
15
  if (needle_len == 1) {
29
9
    char c = needle->data_[0];
30
    // For 'aaa'.find('a', 0, 1)
31
    // end = 1, needle_len = 1, last_start = 1 which means we go through once
32
32
    for (int i = start; i < end; ++i) {
33
28
      if (data_[i] == c) {
34
5
        return i;
35
5
      }
36
28
    }
37
9
  } else {
38
    // Note: this works for finding the empty string.  Empty string is found in
39
    // empty range like [5, 5), but not in [5, 4)
40
41
    // For 'aaa'.find('aa', 0, 2)
42
    // end = 2, needle_len = 2, last_start = 1 which means we go through once
43
44
6
    int last_start = end - needle_len + 1;
45
    // could use a smarter substring search algorithm
46
9
    for (int i = start; i < last_start; ++i) {
47
9
      if (memcmp(data_ + i, needle->data_, needle_len) == 0) {
48
6
        return i;
49
6
      }
50
9
    }
51
6
  }
52
4
  return -1;
53
15
}
54
55
5
int BigStr::rfind(BigStr* needle) {
56
5
  int length = len(this);
57
5
  DCHECK(len(needle) == 1);  // Oils usage
58
0
  char c = needle->data_[0];
59
25
  for (int i = length - 1; i >= 0; --i) {
60
23
    if (data_[i] == c) {
61
3
      return i;
62
3
    }
63
23
  }
64
2
  return -1;
65
5
}
66
67
2
bool BigStr::isdigit() {
68
2
  int n = len(this);
69
2
  if (n == 0) {
70
1
    return false;  // special case
71
1
  }
72
2
  for (int i = 0; i < n; ++i) {
73
1
    if (!::isdigit(data_[i])) {
74
0
      return false;
75
0
    }
76
1
  }
77
1
  return true;
78
1
}
79
80
1
bool BigStr::isalpha() {
81
1
  int n = len(this);
82
1
  if (n == 0) {
83
0
    return false;  // special case
84
0
  }
85
4
  for (int i = 0; i < n; ++i) {
86
3
    if (!::isalpha(data_[i])) {
87
0
      return false;
88
0
    }
89
3
  }
90
1
  return true;
91
1
}
92
93
// e.g. for osh/braces.py
94
4
bool BigStr::isupper() {
95
4
  int n = len(this);
96
4
  if (n == 0) {
97
1
    return false;  // special case
98
1
  }
99
6
  for (int i = 0; i < n; ++i) {
100
4
    if (!::isupper(data_[i])) {
101
1
      return false;
102
1
    }
103
4
  }
104
2
  return true;
105
3
}
106
107
8
bool BigStr::startswith(BigStr* s) {
108
8
  int n = len(s);
109
8
  if (n > len(this)) {
110
0
    return false;
111
0
  }
112
8
  return memcmp(data_, s->data_, n) == 0;
113
8
}
114
115
4
bool BigStr::endswith(BigStr* s) {
116
4
  int len_s = len(s);
117
4
  int len_this = len(this);
118
4
  if (len_s > len_this) {
119
0
    return false;
120
0
  }
121
4
  const char* start = data_ + len_this - len_s;
122
4
  return memcmp(start, s->data_, len_s) == 0;
123
4
}
124
125
// Get a string with one character
126
7
BigStr* BigStr::at(int i) {
127
7
  int length = len(this);
128
7
  if (i < 0) {
129
1
    i = length + i;
130
1
  }
131
7
  DCHECK(0 <= i);
132
7
  DCHECK(i < length);  // had a problem here!
133
134
0
  BigStr* result = NewStr(1);
135
7
  result->data_[0] = data_[i];
136
7
  return result;
137
7
}
138
139
// s[begin:]
140
1
BigStr* BigStr::slice(int begin) {
141
1
  return slice(begin, len(this));
142
1
}
143
144
// s[begin:end]
145
312
BigStr* BigStr::slice(int begin, int end) {
146
312
  int length = len(this);
147
312
  SLICE_ADJUST(begin, end, length);
148
149
312
  DCHECK(0 <= begin && begin <= length);
150
312
  DCHECK(0 <= end && end <= length);
151
152
0
  int new_len = end - begin;
153
312
  DCHECK(0 <= new_len && new_len <= length);
154
155
0
  BigStr* result = NewStr(new_len);  // has kEmptyString optimization
156
312
  memcpy(result->data_, data_ + begin, new_len);
157
158
312
  return result;
159
312
}
160
161
// Used by 'help' builtin and --help, neither of which translate yet.
162
163
0
List<BigStr*>* BigStr::splitlines(bool keep) {
164
0
  DCHECK(keep == true);
165
0
  FAIL(kNotImplemented);
166
0
}
167
168
3
BigStr* BigStr::upper() {
169
3
  int length = len(this);
170
3
  BigStr* result = NewStr(length);
171
3
  char* buffer = result->data();
172
19
  for (int char_index = 0; char_index < length; ++char_index) {
173
16
    buffer[char_index] = toupper(data_[char_index]);
174
16
  }
175
3
  return result;
176
3
}
177
178
3
BigStr* BigStr::lower() {
179
3
  int length = len(this);
180
3
  BigStr* result = NewStr(length);
181
3
  char* buffer = result->data();
182
19
  for (int char_index = 0; char_index < length; ++char_index) {
183
16
    buffer[char_index] = tolower(data_[char_index]);
184
16
  }
185
3
  return result;
186
3
}
187
188
15
BigStr* BigStr::ljust(int width, BigStr* fillchar) {
189
15
  DCHECK(len(fillchar) == 1);
190
191
0
  int length = len(this);
192
15
  int num_fill = width - length;
193
15
  if (num_fill < 0) {
194
5
    return this;
195
10
  } else {
196
10
    BigStr* result = NewStr(width);
197
10
    char c = fillchar->data_[0];
198
10
    memcpy(result->data_, data_, length);
199
21
    for (int i = length; i < width; ++i) {
200
11
      result->data_[i] = c;
201
11
    }
202
10
    return result;
203
10
  }
204
15
}
205
206
15
BigStr* BigStr::rjust(int width, BigStr* fillchar) {
207
15
  DCHECK(len(fillchar) == 1);
208
209
0
  int length = len(this);
210
15
  int num_fill = width - length;
211
15
  if (num_fill < 0) {
212
5
    return this;
213
10
  } else {
214
10
    BigStr* result = NewStr(width);
215
10
    char c = fillchar->data_[0];
216
21
    for (int i = 0; i < num_fill; ++i) {
217
11
      result->data_[i] = c;
218
11
    }
219
10
    memcpy(result->data_ + num_fill, data_, length);
220
10
    return result;
221
10
  }
222
15
}
223
224
362
BigStr* BigStr::replace(BigStr* old, BigStr* new_str) {
225
  // Use -1 as in python2: "aaaa".replace(-1) -> "AAAA"
226
362
  return replace(old, new_str, -1);
227
362
}
228
229
362
BigStr* BigStr::replace(BigStr* old, BigStr* new_str, int count) {
230
  // log("replacing %s with %s", old_data, new_str->data_);
231
362
  const char* old_data = old->data_;
232
233
362
  int this_len = len(this);
234
362
  int old_len = len(old);
235
236
362
  const char* last_possible = data_ + this_len - old_len;
237
238
362
  const char* p_this = data_;  // advances through 'this'
239
240
  // First pass: Calculate number of replacements, and hence new length
241
362
  int replace_count = 0;
242
362
  if (old_len == 0) {
243
0
    replace_count = this_len + 1;
244
0
    if (count > 0) {
245
0
      replace_count = min(replace_count, count);
246
0
    }
247
362
  } else {
248
46.6k
    while (p_this <= last_possible) {
249
46.3k
      if (replace_count != count &&  // limit replacements (if count != -1)
250
46.3k
          memcmp(p_this, old_data, old_len) == 0) {  // equal
251
377
        replace_count++;
252
377
        p_this += old_len;
253
45.9k
      } else {
254
45.9k
        p_this++;
255
45.9k
      }
256
46.3k
    }
257
362
  }
258
259
  // log("replacements %d", replace_count);
260
261
362
  if (replace_count == 0) {
262
1
    return this;  // Reuse the string if there were no replacements
263
1
  }
264
265
361
  int new_str_len = len(new_str);
266
361
  int result_len =
267
361
      this_len - (replace_count * old_len) + (replace_count * new_str_len);
268
269
361
  BigStr* result = NewStr(result_len);
270
271
361
  const char* new_data = new_str->data_;
272
361
  const size_t new_len = new_str_len;
273
274
  // Second pass: Copy pieces into 'result'
275
361
  p_this = data_;                  // back to beginning
276
361
  char* p_result = result->data_;  // advances through 'result'
277
361
  replace_count = 0;
278
279
361
  if (old_len == 0) {
280
    // Should place new_str between each char in this
281
0
    while (p_this < last_possible && replace_count != count) {
282
0
      replace_count++;
283
0
      memcpy(p_result, new_data, new_len);  // Copy from new_str
284
0
      p_result += new_len;                  // Move past new_str
285
286
      // Write a char from this
287
0
      *p_result = *p_this;
288
0
      p_this++;
289
0
      p_result++;
290
0
    }
291
292
0
    if (replace_count != count) {
293
      // Write a copy of new_str at the end
294
0
      assert(p_this == last_possible);
295
0
      memcpy(p_result, new_data, new_len);
296
0
    } else if (p_this <= last_possible) {
297
      // Write the last part of string
298
0
      memcpy(p_result, p_this, data_ + this_len - p_this);
299
0
    }
300
361
  } else {
301
46.6k
    while (p_this <= last_possible) {
302
      // Note: would be more efficient if we remembered the match positions
303
46.3k
      if (replace_count != count &&  // limit replacements (if count != -1)
304
46.3k
          memcmp(p_this, old_data, old_len) == 0) {  // equal
305
377
        memcpy(p_result, new_data, new_len);         // Copy from new_str
306
377
        replace_count++;
307
377
        p_result += new_len;
308
377
        p_this += old_len;
309
45.9k
      } else {  // copy 1 byte
310
45.9k
        *p_result = *p_this;
311
45.9k
        p_result++;
312
45.9k
        p_this++;
313
45.9k
      }
314
46.3k
    }
315
361
    memcpy(p_result, p_this, data_ + this_len - p_this);  // last part of string
316
361
  }
317
318
0
  return result;
319
362
}
320
321
enum class StripWhere {
322
  Left,
323
  Right,
324
  Both,
325
};
326
327
const int kWhitespace = -1;
328
329
80
bool OmitChar(int ch, int what) {
330
80
  if (what == kWhitespace) {
331
    // Intentional incompatibility with Python, where say \v is whitespace
332
    // '\v'.strip() == ''
333
    //
334
    // But it is consistent with the JSON spec [ \t\r\n] and the rules in
335
    // frontend/lexer_def.py
336
    //
337
    // Note that the YSH is separate, and Str => trim() respects Unicode.
338
60
    return IsAsciiWhitespace(ch);
339
60
  } else {
340
20
    return what == ch;
341
20
  }
342
80
}
343
344
// StripAny is modeled after CPython's do_strip() in stringobject.c, and can
345
// implement 6 functions:
346
//
347
//   strip / lstrip / rstrip
348
//   strip(char) / lstrip(char) / rstrip(char)
349
//
350
// Args:
351
//   where: which ends to strip from
352
//   what: kWhitespace, or an ASCII code 0-255
353
354
31
BigStr* StripAny(BigStr* s, StripWhere where, int what) {
355
31
  int length = len(s);
356
31
  const char* char_data = s->data();
357
358
31
  int i = 0;
359
31
  if (where != StripWhere::Right) {
360
46
    while (i < length && OmitChar(char_data[i], what)) {
361
27
      i++;
362
27
    }
363
19
  }
364
365
31
  int j = length;
366
31
  if (where != StripWhere::Left) {
367
47
    do {
368
47
      j--;
369
47
    } while (j >= i && OmitChar(char_data[j], what));
370
22
    j++;
371
22
  }
372
373
31
  if (i == j) {  // Optimization to reuse existing object
374
9
    return kEmptyString;
375
9
  }
376
377
22
  if (i == 0 && j == length) {  // nothing stripped
378
5
    return s;
379
5
  }
380
381
  // Note: makes a copy in leaky version, and will in GC version too
382
17
  int new_len = j - i;
383
17
  BigStr* result = NewStr(new_len);
384
17
  memcpy(result->data(), s->data() + i, new_len);
385
17
  return result;
386
22
}
387
388
10
BigStr* BigStr::strip() {
389
10
  return StripAny(this, StripWhere::Both, kWhitespace);
390
10
}
391
392
// Used for CommandSub in osh/cmd_exec.py
393
4
BigStr* BigStr::rstrip(BigStr* chars) {
394
4
  DCHECK(len(chars) == 1);
395
0
  int c = chars->data_[0];
396
4
  return StripAny(this, StripWhere::Right, c);
397
4
}
398
399
8
BigStr* BigStr::rstrip() {
400
8
  return StripAny(this, StripWhere::Right, kWhitespace);
401
8
}
402
403
4
BigStr* BigStr::lstrip(BigStr* chars) {
404
4
  DCHECK(len(chars) == 1);
405
0
  int c = chars->data_[0];
406
4
  return StripAny(this, StripWhere::Left, c);
407
4
}
408
409
5
BigStr* BigStr::lstrip() {
410
5
  return StripAny(this, StripWhere::Left, kWhitespace);
411
5
}
412
413
10
BigStr* BigStr::join(List<BigStr*>* items) {
414
10
  int length = 0;
415
416
10
  int num_parts = len(items);
417
418
  // " ".join([]) == ""
419
10
  if (num_parts == 0) {
420
4
    return kEmptyString;
421
4
  }
422
423
  // Common case
424
  // 'anything'.join(["foo"]) == "foo"
425
6
  if (num_parts == 1) {
426
2
    return items->at(0);
427
2
  }
428
429
18
  for (int i = 0; i < num_parts; ++i) {
430
14
    length += len(items->at(i));
431
14
  }
432
  // add length of all the separators
433
4
  int this_len = len(this);
434
4
  length += this_len * (num_parts - 1);
435
436
4
  BigStr* result = NewStr(length);
437
4
  char* p_result = result->data_;  // advances through
438
439
18
  for (int i = 0; i < num_parts; ++i) {
440
    // log("i %d", i);
441
14
    if (i != 0 && this_len) {             // optimize common case of ''.join()
442
8
      memcpy(p_result, data_, this_len);  // copy the separator
443
8
      p_result += this_len;
444
      // log("this_len %d", this_len);
445
8
    }
446
447
14
    int n = len(items->at(i));
448
    // log("n: %d", n);
449
14
    memcpy(p_result, items->at(i)->data_, n);  // copy the list item
450
14
    p_result += n;
451
14
  }
452
453
4
  return result;
454
6
}
455
456
49
static void AppendPart(List<BigStr*>* result, BigStr* s, int left, int right) {
457
49
  int new_len = right - left;
458
49
  BigStr* part;
459
49
  if (new_len == 0) {
460
21
    part = kEmptyString;
461
28
  } else {
462
28
    part = NewStr(new_len);
463
28
    memcpy(part->data_, s->data_ + left, new_len);
464
28
  }
465
49
  result->append(part);
466
49
}
467
468
// Split BigStr into List<BigStr*> of parts separated by 'sep'.
469
// The code structure is taken from CPython's Objects/stringlib/split.h.
470
19
List<BigStr*>* BigStr::split(BigStr* sep, int max_split) {
471
19
  DCHECK(sep != nullptr);
472
19
  DCHECK(len(sep) == 1);  // we can only split one char
473
0
  char sep_char = sep->data_[0];
474
475
19
  int str_len = len(this);
476
19
  if (str_len == 0) {
477
    // weird case consistent with Python: ''.split(':') == ['']
478
2
    return NewList<BigStr*>({kEmptyString});
479
2
  }
480
481
17
  List<BigStr*>* result = NewList<BigStr*>({});
482
17
  int left = 0;
483
17
  int right = 0;
484
17
  int num_parts = 0;  // 3 splits results in 4 parts
485
486
57
  while (right < str_len && num_parts < max_split) {
487
    // search for separator
488
93
    for (; right < str_len; right++) {
489
87
      if (data_[right] == sep_char) {
490
34
        AppendPart(result, this, left, right);
491
34
        right++;
492
34
        left = right;
493
34
        num_parts++;
494
34
        break;
495
34
      }
496
87
    }
497
40
  }
498
17
  if (num_parts == 0) {  // Optimization when there is no split
499
2
    result->append(this);
500
15
  } else if (left <= str_len) {  // Last part
501
15
    AppendPart(result, this, left, str_len);
502
15
  }
503
504
17
  return result;
505
19
}
506
507
16
List<BigStr*>* BigStr::split(BigStr* sep) {
508
16
  return this->split(sep, len(this));
509
16
}
510
511
256
unsigned BigStr::hash(HashFunc h) {
512
256
  if (!is_hashed_) {
513
83
    hash_ = h(data_, len(this)) >> 1;
514
83
    is_hashed_ = 1;
515
83
  }
516
256
  return hash_;
517
256
}
518
519
26
static inline BigStr* _StrFormat(const char* fmt, int fmt_len, va_list args) {
520
26
  auto beg = std::cregex_iterator(fmt, fmt + fmt_len, gStrFmtRegex);
521
26
  auto end = std::cregex_iterator();
522
523
26
  char int_buf[kMaxFmtWidth];
524
26
  std::string buf;
525
58
  for (std::cregex_iterator it = beg; it != end; ++it) {
526
58
    const std::cmatch& match = *it;
527
528
58
    const std::csub_match& lit_m = match[1];
529
58
    DCHECK(lit_m.matched);
530
0
    const std::string& lit_s = lit_m.str();
531
58
    buf.append(lit_s);
532
533
58
    int width = 0;
534
58
    bool zero_pad = false;
535
58
    bool pad_back = false;
536
58
    const std::csub_match& width_m = match[2];
537
58
    const std::string& width_s = width_m.str();
538
58
    bool ok = false;
539
58
    if (width_m.matched && !width_s.empty()) {
540
10
      if (width_s[0] == '0') {
541
2
        zero_pad = true;
542
2
        DCHECK(width_s.size() > 1);
543
0
        ok = StringToInt(width_s.c_str() + 1, width_s.size() - 1, 10, &width);
544
2
        DCHECK(ok);
545
0
        (void)ok;  // silence unused var warning in opt
546
8
      } else {
547
8
        ok = StringToInt(width_s.c_str(), width_s.size(), 10, &width);
548
8
        DCHECK(ok);
549
8
      }
550
10
      if (width < 0) {
551
1
        pad_back = true;
552
1
        width *= -1;
553
1
      }
554
10
      DCHECK(0 <= width && width < kMaxFmtWidth);
555
10
    }
556
557
0
    char const* str_to_add = nullptr;
558
58
    int add_len = 0;
559
58
    const std::csub_match& code_m = match[3];
560
58
    const std::string& code_s = code_m.str();
561
58
    if (!code_m.matched) {
562
26
      DCHECK(!width_m.matched);  // python errors on invalid format operators
563
0
      break;
564
26
    }
565
32
    DCHECK(code_s.size() == 1);
566
0
    switch (code_s[0]) {
567
4
    case '%': {
568
4
      str_to_add = code_s.c_str();
569
4
      add_len = 1;
570
4
      break;
571
0
    }
572
10
    case 's': {
573
10
      BigStr* s = va_arg(args, BigStr*);
574
      // Check type unconditionally because mycpp doesn't always check it
575
10
      CHECK(ObjHeader::FromObject(s)->type_tag == TypeTag::BigStr);
576
577
0
      str_to_add = s->data();
578
10
      add_len = len(s);
579
10
      zero_pad = false;  // python ignores the 0 directive for strings
580
10
      break;
581
0
    }
582
7
    case 'r': {
583
7
      BigStr* s = va_arg(args, BigStr*);
584
      // Check type unconditionally because mycpp doesn't always check it
585
7
      CHECK(ObjHeader::FromObject(s)->type_tag == TypeTag::BigStr);
586
587
0
      s = repr(s);
588
7
      str_to_add = s->data();
589
7
      add_len = len(s);
590
7
      zero_pad = false;  // python ignores the 0 directive for strings
591
7
      break;
592
0
    }
593
8
    case 'd':  // fallthrough
594
11
    case 'o': {
595
11
      int d = va_arg(args, int);
596
11
      add_len = snprintf(int_buf, kMaxFmtWidth,
597
11
                         match.str().c_str() + lit_s.size(), d);
598
11
      DCHECK(add_len > 0);
599
0
      str_to_add = int_buf;
600
11
      break;
601
8
    }
602
0
    default:
603
0
      DCHECK(0);
604
0
      break;
605
32
    }
606
32
    DCHECK(str_to_add != nullptr);
607
608
32
    if (pad_back) {
609
1
      buf.append(str_to_add, add_len);
610
1
    }
611
32
    if (add_len < width) {
612
21
      for (int i = 0; i < width - add_len; ++i) {
613
18
        buf.push_back(zero_pad ? '0' : ' ');
614
18
      }
615
3
    }
616
32
    if (!pad_back) {
617
31
      buf.append(str_to_add, add_len);
618
31
    }
619
32
  }
620
621
26
  return StrFromC(buf.c_str(), buf.size());
622
26
}
623
624
4
BigStr* StrIter::Value() {  // similar to at()
625
4
  BigStr* result = NewStr(1);
626
4
  result->data_[0] = s_->data_[i_];
627
4
  DCHECK(result->data_[1] == '\0');
628
0
  return result;
629
4
}
630
631
24
BigStr* StrFormat(const char* fmt, ...) {
632
24
  va_list args;
633
24
  va_start(args, fmt);
634
24
  BigStr* ret = _StrFormat(fmt, strlen(fmt), args);
635
24
  va_end(args);
636
24
  return ret;
637
24
}
638
639
2
BigStr* StrFormat(BigStr* fmt, ...) {
640
2
  va_list args;
641
2
  va_start(args, fmt);
642
2
  BigStr* ret = _StrFormat(fmt->data(), len(fmt), args);
643
2
  va_end(args);
644
2
  return ret;
645
2
}