/home/uke/oil/mycpp/gc_str.cc

Source (jump to first uncovered line)
#include "mycpp/gc_str.h"

#include <ctype.h>  // isalpha(), isdigit()
#include <stdarg.h>

#include <regex>

#include "mycpp/common.h"
#include "mycpp/gc_alloc.h"     // NewStr()
#include "mycpp/gc_builtins.h"  // StringToInt()
#include "mycpp/gc_list.h"      // join(), split() use it

GLOBAL_STR(kEmptyString, "");

static const std::regex gStrFmtRegex("([^%]*)(?:%(-?[0-9]*)(.))?");
static const int kMaxFmtWidth = 256;  // arbitrary...

int BigStr::find(BigStr* needle, int start, int end) {
  if (end == -1) {
    end = len(this);
  }
  int needle_len = len(needle);

  if (needle_len > (end - start)) {
    return -1;  // needle is too long to be found (Python behavior)
  }

  if (needle_len == 1) {
    char c = needle->data_[0];
    // For 'aaa'.find('a', 0, 1)
    // end = 1, needle_len = 1, last_start = 1 which means we go through once
    for (int i = start; i < end; ++i) {
      if (data_[i] == c) {
        return i;
      }
    }
  } else {
    // Note: this works for finding the empty string.  Empty string is found in
    // empty range like [5, 5), but not in [5, 4)

    // For 'aaa'.find('aa', 0, 2)
    // end = 2, needle_len = 2, last_start = 1 which means we go through once

    int last_start = end - needle_len + 1;
    // could use a smarter substring search algorithm
    for (int i = start; i < last_start; ++i) {
      if (memcmp(data_ + i, needle->data_, needle_len) == 0) {
        return i;
      }
    }
  }
  return -1;
}

int BigStr::rfind(BigStr* needle) {
  int length = len(this);
  DCHECK(len(needle) == 1);  // Oils usage
  char c = needle->data_[0];
  for (int i = length - 1; i >= 0; --i) {
    if (data_[i] == c) {
      return i;
    }
  }
  return -1;
}

bool BigStr::isdigit() {
  int n = len(this);
  if (n == 0) {
    return false;  // special case
  }
  for (int i = 0; i < n; ++i) {
    if (!::isdigit(data_[i])) {
      return false;
    }
  }
  return true;
}

bool BigStr::isalpha() {
  int n = len(this);
  if (n == 0) {
    return false;  // special case
  }
  for (int i = 0; i < n; ++i) {
    if (!::isalpha(data_[i])) {
      return false;
    }
  }
  return true;
}

// e.g. for osh/braces.py
bool BigStr::isupper() {
  int n = len(this);
  if (n == 0) {
    return false;  // special case
  }
  for (int i = 0; i < n; ++i) {
    if (!::isupper(data_[i])) {
      return false;
    }
  }
  return true;
}

bool BigStr::startswith(BigStr* s) {
  int n = len(s);
  if (n > len(this)) {
    return false;
  }
  return memcmp(data_, s->data_, n) == 0;
}

bool BigStr::endswith(BigStr* s) {
  int len_s = len(s);
  int len_this = len(this);
  if (len_s > len_this) {
    return false;
  }
  const char* start = data_ + len_this - len_s;
  return memcmp(start, s->data_, len_s) == 0;
}

// Get a string with one character
BigStr* BigStr::at(int i) {
  int length = len(this);
  if (i < 0) {
    i = length + i;
  }
  DCHECK(0 <= i);
  DCHECK(i < length);  // had a problem here!

  BigStr* result = NewStr(1);
  result->data_[0] = data_[i];
  return result;
}

// s[begin:]
BigStr* BigStr::slice(int begin) {
  return slice(begin, len(this));
}

// s[begin:end]
BigStr* BigStr::slice(int begin, int end) {
  int length = len(this);
  SLICE_ADJUST(begin, end, length);

  DCHECK(0 <= begin && begin <= length);
  DCHECK(0 <= end && end <= length);

  int new_len = end - begin;
  DCHECK(0 <= new_len && new_len <= length);

  BigStr* result = NewStr(new_len);  // has kEmptyString optimization
  memcpy(result->data_, data_ + begin, new_len);

  return result;
}

// Used by 'help' builtin and --help, neither of which translate yet.

List<BigStr*>* BigStr::splitlines(bool keep) {
  DCHECK(keep == true);
  FAIL(kNotImplemented);
}

BigStr* BigStr::upper() {
  int length = len(this);
  BigStr* result = NewStr(length);
  char* buffer = result->data();
  for (int char_index = 0; char_index < length; ++char_index) {
    buffer[char_index] = toupper(data_[char_index]);
  }
  return result;
}

BigStr* BigStr::lower() {
  int length = len(this);
  BigStr* result = NewStr(length);
  char* buffer = result->data();
  for (int char_index = 0; char_index < length; ++char_index) {
    buffer[char_index] = tolower(data_[char_index]);
  }
  return result;
}

BigStr* BigStr::ljust(int width, BigStr* fillchar) {
  DCHECK(len(fillchar) == 1);

  int length = len(this);
  int num_fill = width - length;
  if (num_fill < 0) {
    return this;
  } else {
    BigStr* result = NewStr(width);
    char c = fillchar->data_[0];
    memcpy(result->data_, data_, length);
    for (int i = length; i < width; ++i) {
      result->data_[i] = c;
    }
    return result;
  }
}

BigStr* BigStr::rjust(int width, BigStr* fillchar) {
  DCHECK(len(fillchar) == 1);

  int length = len(this);
  int num_fill = width - length;
  if (num_fill < 0) {
    return this;
  } else {
    BigStr* result = NewStr(width);
    char c = fillchar->data_[0];
    for (int i = 0; i < num_fill; ++i) {
      result->data_[i] = c;
    }
    memcpy(result->data_ + num_fill, data_, length);
    return result;
  }
}

BigStr* BigStr::replace(BigStr* old, BigStr* new_str) {
  // Use -1 as in python2: "aaaa".replace(-1) -> "AAAA"
  return replace(old, new_str, -1);
}

BigStr* BigStr::replace(BigStr* old, BigStr* new_str, int count) {
  // log("replacing %s with %s", old_data, new_str->data_);
  const char* old_data = old->data_;

  int this_len = len(this);
  int old_len = len(old);

  const char* last_possible = data_ + this_len - old_len;

  const char* p_this = data_;  // advances through 'this'

  // First pass: Calculate number of replacements, and hence new length
  int replace_count = 0;
  if (old_len == 0) {
    replace_count = this_len + 1;
    if (count > 0) {
      replace_count = min(replace_count, count);
    }
  } else {
    while (p_this <= last_possible) {
      if (replace_count != count &&  // limit replacements (if count != -1)
          memcmp(p_this, old_data, old_len) == 0) {  // equal
        replace_count++;
        p_this += old_len;
      } else {
        p_this++;
      }
    }
  }

  // log("replacements %d", replace_count);

  if (replace_count == 0) {
    return this;  // Reuse the string if there were no replacements
  }

  int new_str_len = len(new_str);
  int result_len =
      this_len - (replace_count * old_len) + (replace_count * new_str_len);

  BigStr* result = NewStr(result_len);

  const char* new_data = new_str->data_;
  const size_t new_len = new_str_len;

  // Second pass: Copy pieces into 'result'
  p_this = data_;                  // back to beginning
  char* p_result = result->data_;  // advances through 'result'
  replace_count = 0;

  if (old_len == 0) {
    // Should place new_str between each char in this
    while (p_this < last_possible && replace_count != count) {
      replace_count++;
      memcpy(p_result, new_data, new_len);  // Copy from new_str
      p_result += new_len;                  // Move past new_str

      // Write a char from this
      *p_result = *p_this;
      p_this++;
      p_result++;
    }

    if (replace_count != count) {
      // Write a copy of new_str at the end
      assert(p_this == last_possible);
      memcpy(p_result, new_data, new_len);
    } else if (p_this <= last_possible) {
      // Write the last part of string
      memcpy(p_result, p_this, data_ + this_len - p_this);
    }
  } else {
    while (p_this <= last_possible) {
      // Note: would be more efficient if we remembered the match positions
      if (replace_count != count &&  // limit replacements (if count != -1)
          memcmp(p_this, old_data, old_len) == 0) {  // equal
        memcpy(p_result, new_data, new_len);         // Copy from new_str
        replace_count++;
        p_result += new_len;
        p_this += old_len;
      } else {  // copy 1 byte
        *p_result = *p_this;
        p_result++;
        p_this++;
      }
    }
    memcpy(p_result, p_this, data_ + this_len - p_this);  // last part of string
  }

  return result;
}

enum class StripWhere {
  Left,
  Right,
  Both,
};

const int kWhitespace = -1;

bool OmitChar(int ch, int what) {
  if (what == kWhitespace) {
    // Intentional incompatibility with Python, where say \v is whitespace
    // '\v'.strip() == ''
    //
    // But it is consistent with the JSON spec [ \t\r\n] and the rules in
    // frontend/lexer_def.py
    //
    // Note that the YSH is separate, and Str => trim() respects Unicode.
    return IsAsciiWhitespace(ch);
  } else {
    return what == ch;
  }
}

// StripAny is modeled after CPython's do_strip() in stringobject.c, and can
// implement 6 functions:
//
//   strip / lstrip / rstrip
//   strip(char) / lstrip(char) / rstrip(char)
//
// Args:
//   where: which ends to strip from
//   what: kWhitespace, or an ASCII code 0-255

BigStr* StripAny(BigStr* s, StripWhere where, int what) {
  int length = len(s);
  const char* char_data = s->data();

  int i = 0;
  if (where != StripWhere::Right) {
    while (i < length && OmitChar(char_data[i], what)) {
      i++;
    }
  }

  int j = length;
  if (where != StripWhere::Left) {
    do {
      j--;
    } while (j >= i && OmitChar(char_data[j], what));
    j++;
  }

  if (i == j) {  // Optimization to reuse existing object
    return kEmptyString;
  }

  if (i == 0 && j == length) {  // nothing stripped
    return s;
  }

  // Note: makes a copy in leaky version, and will in GC version too
  int new_len = j - i;
  BigStr* result = NewStr(new_len);
  memcpy(result->data(), s->data() + i, new_len);
  return result;
}

BigStr* BigStr::strip() {
  return StripAny(this, StripWhere::Both, kWhitespace);
}

// Used for CommandSub in osh/cmd_exec.py
BigStr* BigStr::rstrip(BigStr* chars) {
  DCHECK(len(chars) == 1);
  int c = chars->data_[0];
  return StripAny(this, StripWhere::Right, c);
}

BigStr* BigStr::rstrip() {
  return StripAny(this, StripWhere::Right, kWhitespace);
}

BigStr* BigStr::lstrip(BigStr* chars) {
  DCHECK(len(chars) == 1);
  int c = chars->data_[0];
  return StripAny(this, StripWhere::Left, c);
}

BigStr* BigStr::lstrip() {
  return StripAny(this, StripWhere::Left, kWhitespace);
}

BigStr* BigStr::join(List<BigStr*>* items) {
  int length = 0;

  int num_parts = len(items);

  // " ".join([]) == ""
  if (num_parts == 0) {
    return kEmptyString;
  }

  // Common case
  // 'anything'.join(["foo"]) == "foo"
  if (num_parts == 1) {
    return items->at(0);
  }

  for (int i = 0; i < num_parts; ++i) {
    length += len(items->at(i));
  }
  // add length of all the separators
  int this_len = len(this);
  length += this_len * (num_parts - 1);

  BigStr* result = NewStr(length);
  char* p_result = result->data_;  // advances through

  for (int i = 0; i < num_parts; ++i) {
    // log("i %d", i);
    if (i != 0 && this_len) {             // optimize common case of ''.join()
      memcpy(p_result, data_, this_len);  // copy the separator
      p_result += this_len;
      // log("this_len %d", this_len);
    }

    int n = len(items->at(i));
    // log("n: %d", n);
    memcpy(p_result, items->at(i)->data_, n);  // copy the list item
    p_result += n;
  }

  return result;
}

static void AppendPart(List<BigStr*>* result, BigStr* s, int left, int right) {
  int new_len = right - left;
  BigStr* part;
  if (new_len == 0) {
    part = kEmptyString;
  } else {
    part = NewStr(new_len);
    memcpy(part->data_, s->data_ + left, new_len);
  }
  result->append(part);
}

// Split BigStr into List<BigStr*> of parts separated by 'sep'.
// The code structure is taken from CPython's Objects/stringlib/split.h.
List<BigStr*>* BigStr::split(BigStr* sep, int max_split) {
  DCHECK(sep != nullptr);
  DCHECK(len(sep) == 1);  // we can only split one char
  char sep_char = sep->data_[0];

  int str_len = len(this);
  if (str_len == 0) {
    // weird case consistent with Python: ''.split(':') == ['']
    return NewList<BigStr*>({kEmptyString});
  }

  List<BigStr*>* result = NewList<BigStr*>({});
  int left = 0;
  int right = 0;
  int num_parts = 0;  // 3 splits results in 4 parts

  while (right < str_len && num_parts < max_split) {
    // search for separator
    for (; right < str_len; right++) {
      if (data_[right] == sep_char) {
        AppendPart(result, this, left, right);
        right++;
        left = right;
        num_parts++;
        break;
      }
    }
  }
  if (num_parts == 0) {  // Optimization when there is no split
    result->append(this);
  } else if (left <= str_len) {  // Last part
    AppendPart(result, this, left, str_len);
  }

  return result;
}

List<BigStr*>* BigStr::split(BigStr* sep) {
  return this->split(sep, len(this));
}

unsigned BigStr::hash(HashFunc h) {
  if (!is_hashed_) {
    hash_ = h(data_, len(this)) >> 1;
    is_hashed_ = 1;
  }
  return hash_;
}

static inline BigStr* _StrFormat(const char* fmt, int fmt_len, va_list args) {
  auto beg = std::cregex_iterator(fmt, fmt + fmt_len, gStrFmtRegex);
  auto end = std::cregex_iterator();

  char int_buf[kMaxFmtWidth];
  std::string buf;
  for (std::cregex_iterator it = beg; it != end; ++it) {
    const std::cmatch& match = *it;

    const std::csub_match& lit_m = match[1];
    DCHECK(lit_m.matched);
    const std::string& lit_s = lit_m.str();
    buf.append(lit_s);

    int width = 0;
    bool zero_pad = false;
    bool pad_back = false;
    const std::csub_match& width_m = match[2];
    const std::string& width_s = width_m.str();
    bool ok = false;
    if (width_m.matched && !width_s.empty()) {
      if (width_s[0] == '0') {
        zero_pad = true;
        DCHECK(width_s.size() > 1);
        ok = StringToInt(width_s.c_str() + 1, width_s.size() - 1, 10, &width);
        DCHECK(ok);
        (void)ok;  // silence unused var warning in opt
      } else {
        ok = StringToInt(width_s.c_str(), width_s.size(), 10, &width);
        DCHECK(ok);
      }
      if (width < 0) {
        pad_back = true;
        width *= -1;
      }
      DCHECK(0 <= width && width < kMaxFmtWidth);
    }

    char const* str_to_add = nullptr;
    int add_len = 0;
    const std::csub_match& code_m = match[3];
    const std::string& code_s = code_m.str();
    if (!code_m.matched) {
      DCHECK(!width_m.matched);  // python errors on invalid format operators
      break;
    }
    DCHECK(code_s.size() == 1);
    switch (code_s[0]) {
    case '%': {
      str_to_add = code_s.c_str();
      add_len = 1;
      break;
    }
    case 's': {
      BigStr* s = va_arg(args, BigStr*);
      // Check type unconditionally because mycpp doesn't always check it
      CHECK(ObjHeader::FromObject(s)->type_tag == TypeTag::BigStr);

      str_to_add = s->data();
      add_len = len(s);
      zero_pad = false;  // python ignores the 0 directive for strings
      break;
    }
    case 'r': {
      BigStr* s = va_arg(args, BigStr*);
      // Check type unconditionally because mycpp doesn't always check it
      CHECK(ObjHeader::FromObject(s)->type_tag == TypeTag::BigStr);

      s = repr(s);
      str_to_add = s->data();
      add_len = len(s);
      zero_pad = false;  // python ignores the 0 directive for strings
      break;
    }
    case 'd':  // fallthrough
    case 'o': {
      int d = va_arg(args, int);
      add_len = snprintf(int_buf, kMaxFmtWidth,
                         match.str().c_str() + lit_s.size(), d);
      DCHECK(add_len > 0);
      str_to_add = int_buf;
      break;
    }
    default:
      DCHECK(0);
      break;
    }
    DCHECK(str_to_add != nullptr);

    if (pad_back) {
      buf.append(str_to_add, add_len);
    }
    if (add_len < width) {
      for (int i = 0; i < width - add_len; ++i) {
        buf.push_back(zero_pad ? '0' : ' ');
      }
    }
    if (!pad_back) {
      buf.append(str_to_add, add_len);
    }
  }

  return StrFromC(buf.c_str(), buf.size());
}

BigStr* StrIter::Value() {  // similar to at()
  BigStr* result = NewStr(1);
  result->data_[0] = s_->data_[i_];
  DCHECK(result->data_[1] == '\0');
  return result;
}

BigStr* StrFormat(const char* fmt, ...) {
  va_list args;
  va_start(args, fmt);
  BigStr* ret = _StrFormat(fmt, strlen(fmt), args);
  va_end(args);
  return ret;
}

BigStr* StrFormat(BigStr* fmt, ...) {
  va_list args;
  va_start(args, fmt);
  BigStr* ret = _StrFormat(fmt->data(), len(fmt), args);
  va_end(args);
  return ret;
}

cpp

Coverage Report

Created: 2024-07-28 06:14

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