string_util_internal.h 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612
  1. // Copyright 2020 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef BASE_STRINGS_STRING_UTIL_INTERNAL_H_
  5. #define BASE_STRINGS_STRING_UTIL_INTERNAL_H_
  6. #include <algorithm>
  7. #include "base/check.h"
  8. #include "base/check_op.h"
  9. #include "base/logging.h"
  10. #include "base/notreached.h"
  11. #include "base/ranges/algorithm.h"
  12. #include "base/strings/string_piece.h"
  13. #include "base/third_party/icu/icu_utf.h"
  14. namespace base {
  15. namespace internal {
  16. // Used by ReplaceStringPlaceholders to track the position in the string of
  17. // replaced parameters.
  18. struct ReplacementOffset {
  19. ReplacementOffset(uintptr_t parameter, size_t offset)
  20. : parameter(parameter), offset(offset) {}
  21. // Index of the parameter.
  22. size_t parameter;
  23. // Starting position in the string.
  24. size_t offset;
  25. };
  26. static bool CompareParameter(const ReplacementOffset& elem1,
  27. const ReplacementOffset& elem2) {
  28. return elem1.parameter < elem2.parameter;
  29. }
  30. // Assuming that a pointer is the size of a "machine word", then
  31. // uintptr_t is an integer type that is also a machine word.
  32. using MachineWord = uintptr_t;
  33. inline bool IsMachineWordAligned(const void* pointer) {
  34. return !(reinterpret_cast<MachineWord>(pointer) & (sizeof(MachineWord) - 1));
  35. }
  36. template <typename T, typename CharT = typename T::value_type>
  37. std::basic_string<CharT> ToLowerASCIIImpl(T str) {
  38. std::basic_string<CharT> ret;
  39. ret.reserve(str.size());
  40. for (size_t i = 0; i < str.size(); i++)
  41. ret.push_back(ToLowerASCII(str[i]));
  42. return ret;
  43. }
  44. template <typename T, typename CharT = typename T::value_type>
  45. std::basic_string<CharT> ToUpperASCIIImpl(T str) {
  46. std::basic_string<CharT> ret;
  47. ret.reserve(str.size());
  48. for (size_t i = 0; i < str.size(); i++)
  49. ret.push_back(ToUpperASCII(str[i]));
  50. return ret;
  51. }
  52. template <typename T, typename CharT = typename T::value_type>
  53. int CompareCaseInsensitiveASCIIT(T a, T b) {
  54. // Find the first characters that aren't equal and compare them. If the end
  55. // of one of the strings is found before a nonequal character, the lengths
  56. // of the strings are compared.
  57. size_t i = 0;
  58. while (i < a.length() && i < b.length()) {
  59. CharT lower_a = ToLowerASCII(a[i]);
  60. CharT lower_b = ToLowerASCII(b[i]);
  61. if (lower_a < lower_b)
  62. return -1;
  63. if (lower_a > lower_b)
  64. return 1;
  65. i++;
  66. }
  67. // End of one string hit before finding a different character. Expect the
  68. // common case to be "strings equal" at this point so check that first.
  69. if (a.length() == b.length())
  70. return 0;
  71. if (a.length() < b.length())
  72. return -1;
  73. return 1;
  74. }
  75. template <typename T, typename CharT = typename T::value_type>
  76. TrimPositions TrimStringT(T input,
  77. T trim_chars,
  78. TrimPositions positions,
  79. std::basic_string<CharT>* output) {
  80. // Find the edges of leading/trailing whitespace as desired. Need to use
  81. // a StringPiece version of input to be able to call find* on it with the
  82. // StringPiece version of trim_chars (normally the trim_chars will be a
  83. // constant so avoid making a copy).
  84. const size_t last_char = input.length() - 1;
  85. const size_t first_good_char =
  86. (positions & TRIM_LEADING) ? input.find_first_not_of(trim_chars) : 0;
  87. const size_t last_good_char = (positions & TRIM_TRAILING)
  88. ? input.find_last_not_of(trim_chars)
  89. : last_char;
  90. // When the string was all trimmed, report that we stripped off characters
  91. // from whichever position the caller was interested in. For empty input, we
  92. // stripped no characters, but we still need to clear |output|.
  93. if (input.empty() || first_good_char == std::basic_string<CharT>::npos ||
  94. last_good_char == std::basic_string<CharT>::npos) {
  95. bool input_was_empty = input.empty(); // in case output == &input
  96. output->clear();
  97. return input_was_empty ? TRIM_NONE : positions;
  98. }
  99. // Trim.
  100. output->assign(input.data() + first_good_char,
  101. last_good_char - first_good_char + 1);
  102. // Return where we trimmed from.
  103. return static_cast<TrimPositions>(
  104. (first_good_char == 0 ? TRIM_NONE : TRIM_LEADING) |
  105. (last_good_char == last_char ? TRIM_NONE : TRIM_TRAILING));
  106. }
  107. template <typename T, typename CharT = typename T::value_type>
  108. T TrimStringPieceT(T input, T trim_chars, TrimPositions positions) {
  109. size_t begin =
  110. (positions & TRIM_LEADING) ? input.find_first_not_of(trim_chars) : 0;
  111. size_t end = (positions & TRIM_TRAILING)
  112. ? input.find_last_not_of(trim_chars) + 1
  113. : input.size();
  114. return input.substr(std::min(begin, input.size()), end - begin);
  115. }
  116. template <typename T, typename CharT = typename T::value_type>
  117. std::basic_string<CharT> CollapseWhitespaceT(
  118. T text,
  119. bool trim_sequences_with_line_breaks) {
  120. std::basic_string<CharT> result;
  121. result.resize(text.size());
  122. // Set flags to pretend we're already in a trimmed whitespace sequence, so we
  123. // will trim any leading whitespace.
  124. bool in_whitespace = true;
  125. bool already_trimmed = true;
  126. size_t chars_written = 0;
  127. for (auto c : text) {
  128. if (IsUnicodeWhitespace(c)) {
  129. if (!in_whitespace) {
  130. // Reduce all whitespace sequences to a single space.
  131. in_whitespace = true;
  132. result[chars_written++] = L' ';
  133. }
  134. if (trim_sequences_with_line_breaks && !already_trimmed &&
  135. ((c == '\n') || (c == '\r'))) {
  136. // Whitespace sequences containing CR or LF are eliminated entirely.
  137. already_trimmed = true;
  138. --chars_written;
  139. }
  140. } else {
  141. // Non-whitespace characters are copied straight across.
  142. in_whitespace = false;
  143. already_trimmed = false;
  144. result[chars_written++] = c;
  145. }
  146. }
  147. if (in_whitespace && !already_trimmed) {
  148. // Any trailing whitespace is eliminated.
  149. --chars_written;
  150. }
  151. result.resize(chars_written);
  152. return result;
  153. }
  154. template <class Char>
  155. bool DoIsStringASCII(const Char* characters, size_t length) {
  156. // Bitmasks to detect non ASCII characters for character sizes of 8, 16 and 32
  157. // bits.
  158. constexpr MachineWord NonASCIIMasks[] = {
  159. 0, MachineWord(0x8080808080808080ULL), MachineWord(0xFF80FF80FF80FF80ULL),
  160. 0, MachineWord(0xFFFFFF80FFFFFF80ULL),
  161. };
  162. if (!length)
  163. return true;
  164. constexpr MachineWord non_ascii_bit_mask = NonASCIIMasks[sizeof(Char)];
  165. static_assert(non_ascii_bit_mask, "Error: Invalid Mask");
  166. MachineWord all_char_bits = 0;
  167. const Char* end = characters + length;
  168. // Prologue: align the input.
  169. while (!IsMachineWordAligned(characters) && characters < end)
  170. all_char_bits |= static_cast<MachineWord>(*characters++);
  171. if (all_char_bits & non_ascii_bit_mask)
  172. return false;
  173. // Compare the values of CPU word size.
  174. constexpr size_t chars_per_word = sizeof(MachineWord) / sizeof(Char);
  175. constexpr int batch_count = 16;
  176. while (characters <= end - batch_count * chars_per_word) {
  177. all_char_bits = 0;
  178. for (int i = 0; i < batch_count; ++i) {
  179. all_char_bits |= *(reinterpret_cast<const MachineWord*>(characters));
  180. characters += chars_per_word;
  181. }
  182. if (all_char_bits & non_ascii_bit_mask)
  183. return false;
  184. }
  185. // Process the remaining words.
  186. all_char_bits = 0;
  187. while (characters <= end - chars_per_word) {
  188. all_char_bits |= *(reinterpret_cast<const MachineWord*>(characters));
  189. characters += chars_per_word;
  190. }
  191. // Process the remaining bytes.
  192. while (characters < end)
  193. all_char_bits |= static_cast<MachineWord>(*characters++);
  194. return !(all_char_bits & non_ascii_bit_mask);
  195. }
  196. template <bool (*Validator)(base_icu::UChar32)>
  197. inline bool DoIsStringUTF8(StringPiece str) {
  198. const uint8_t* src = reinterpret_cast<const uint8_t*>(str.data());
  199. size_t src_len = str.length();
  200. size_t char_index = 0;
  201. while (char_index < src_len) {
  202. base_icu::UChar32 code_point;
  203. CBU8_NEXT(src, char_index, src_len, code_point);
  204. if (!Validator(code_point))
  205. return false;
  206. }
  207. return true;
  208. }
  209. template <typename T, typename CharT = typename T::value_type>
  210. bool StartsWithT(T str, T search_for, CompareCase case_sensitivity) {
  211. if (search_for.size() > str.size())
  212. return false;
  213. BasicStringPiece<CharT> source = str.substr(0, search_for.size());
  214. switch (case_sensitivity) {
  215. case CompareCase::SENSITIVE:
  216. return source == search_for;
  217. case CompareCase::INSENSITIVE_ASCII:
  218. return std::equal(search_for.begin(), search_for.end(), source.begin(),
  219. CaseInsensitiveCompareASCII<CharT>());
  220. default:
  221. NOTREACHED();
  222. return false;
  223. }
  224. }
  225. template <typename T, typename CharT = typename T::value_type>
  226. bool EndsWithT(T str, T search_for, CompareCase case_sensitivity) {
  227. if (search_for.size() > str.size())
  228. return false;
  229. BasicStringPiece<CharT> source =
  230. str.substr(str.size() - search_for.size(), search_for.size());
  231. switch (case_sensitivity) {
  232. case CompareCase::SENSITIVE:
  233. return source == search_for;
  234. case CompareCase::INSENSITIVE_ASCII:
  235. return std::equal(source.begin(), source.end(), search_for.begin(),
  236. CaseInsensitiveCompareASCII<CharT>());
  237. default:
  238. NOTREACHED();
  239. return false;
  240. }
  241. }
  242. // A Matcher for DoReplaceMatchesAfterOffset() that matches substrings.
  243. template <class CharT>
  244. struct SubstringMatcher {
  245. BasicStringPiece<CharT> find_this;
  246. size_t Find(const std::basic_string<CharT>& input, size_t pos) {
  247. return input.find(find_this.data(), pos, find_this.length());
  248. }
  249. size_t MatchSize() { return find_this.length(); }
  250. };
  251. // Type deduction helper for SubstringMatcher.
  252. template <typename T, typename CharT = typename T::value_type>
  253. auto MakeSubstringMatcher(T find_this) {
  254. return SubstringMatcher<CharT>{find_this};
  255. }
  256. // A Matcher for DoReplaceMatchesAfterOffset() that matches single characters.
  257. template <class CharT>
  258. struct CharacterMatcher {
  259. BasicStringPiece<CharT> find_any_of_these;
  260. size_t Find(const std::basic_string<CharT>& input, size_t pos) {
  261. return input.find_first_of(find_any_of_these.data(), pos,
  262. find_any_of_these.length());
  263. }
  264. constexpr size_t MatchSize() { return 1; }
  265. };
  266. // Type deduction helper for CharacterMatcher.
  267. template <typename T, typename CharT = typename T::value_type>
  268. auto MakeCharacterMatcher(T find_any_of_these) {
  269. return CharacterMatcher<CharT>{find_any_of_these};
  270. }
  271. enum class ReplaceType { REPLACE_ALL, REPLACE_FIRST };
  272. // Runs in O(n) time in the length of |str|, and transforms the string without
  273. // reallocating when possible. Returns |true| if any matches were found.
  274. //
  275. // This is parameterized on a |Matcher| traits type, so that it can be the
  276. // implementation for both ReplaceChars() and ReplaceSubstringsAfterOffset().
  277. template <typename Matcher, typename T, typename CharT = typename T::value_type>
  278. bool DoReplaceMatchesAfterOffset(std::basic_string<CharT>* str,
  279. size_t initial_offset,
  280. Matcher matcher,
  281. T replace_with,
  282. ReplaceType replace_type) {
  283. using CharTraits = std::char_traits<CharT>;
  284. const size_t find_length = matcher.MatchSize();
  285. if (!find_length)
  286. return false;
  287. // If the find string doesn't appear, there's nothing to do.
  288. size_t first_match = matcher.Find(*str, initial_offset);
  289. if (first_match == std::basic_string<CharT>::npos)
  290. return false;
  291. // If we're only replacing one instance, there's no need to do anything
  292. // complicated.
  293. const size_t replace_length = replace_with.length();
  294. if (replace_type == ReplaceType::REPLACE_FIRST) {
  295. str->replace(first_match, find_length, replace_with.data(), replace_length);
  296. return true;
  297. }
  298. // If the find and replace strings are the same length, we can simply use
  299. // replace() on each instance, and finish the entire operation in O(n) time.
  300. if (find_length == replace_length) {
  301. auto* buffer = &((*str)[0]);
  302. for (size_t offset = first_match; offset != std::basic_string<CharT>::npos;
  303. offset = matcher.Find(*str, offset + replace_length)) {
  304. CharTraits::copy(buffer + offset, replace_with.data(), replace_length);
  305. }
  306. return true;
  307. }
  308. // Since the find and replace strings aren't the same length, a loop like the
  309. // one above would be O(n^2) in the worst case, as replace() will shift the
  310. // entire remaining string each time. We need to be more clever to keep things
  311. // O(n).
  312. //
  313. // When the string is being shortened, it's possible to just shift the matches
  314. // down in one pass while finding, and truncate the length at the end of the
  315. // search.
  316. //
  317. // If the string is being lengthened, more work is required. The strategy used
  318. // here is to make two find() passes through the string. The first pass counts
  319. // the number of matches to determine the new size. The second pass will
  320. // either construct the new string into a new buffer (if the existing buffer
  321. // lacked capacity), or else -- if there is room -- create a region of scratch
  322. // space after |first_match| by shifting the tail of the string to a higher
  323. // index, and doing in-place moves from the tail to lower indices thereafter.
  324. size_t str_length = str->length();
  325. size_t expansion = 0;
  326. if (replace_length > find_length) {
  327. // This operation lengthens the string; determine the new length by counting
  328. // matches.
  329. const size_t expansion_per_match = (replace_length - find_length);
  330. size_t num_matches = 0;
  331. for (size_t match = first_match; match != std::basic_string<CharT>::npos;
  332. match = matcher.Find(*str, match + find_length)) {
  333. expansion += expansion_per_match;
  334. ++num_matches;
  335. }
  336. const size_t final_length = str_length + expansion;
  337. if (str->capacity() < final_length) {
  338. // If we'd have to allocate a new buffer to grow the string, build the
  339. // result directly into the new allocation via append().
  340. std::basic_string<CharT> src(str->get_allocator());
  341. str->swap(src);
  342. str->reserve(final_length);
  343. size_t pos = 0;
  344. for (size_t match = first_match;; match = matcher.Find(src, pos)) {
  345. str->append(src, pos, match - pos);
  346. str->append(replace_with.data(), replace_length);
  347. pos = match + find_length;
  348. // A mid-loop test/break enables skipping the final Find() call; the
  349. // number of matches is known, so don't search past the last one.
  350. if (!--num_matches)
  351. break;
  352. }
  353. // Handle substring after the final match.
  354. str->append(src, pos, str_length - pos);
  355. return true;
  356. }
  357. // Prepare for the copy/move loop below -- expand the string to its final
  358. // size by shifting the data after the first match to the end of the resized
  359. // string.
  360. size_t shift_src = first_match + find_length;
  361. size_t shift_dst = shift_src + expansion;
  362. // Big |expansion| factors (relative to |str_length|) require padding up to
  363. // |shift_dst|.
  364. if (shift_dst > str_length)
  365. str->resize(shift_dst);
  366. str->replace(shift_dst, str_length - shift_src, *str, shift_src,
  367. str_length - shift_src);
  368. str_length = final_length;
  369. }
  370. // We can alternate replacement and move operations. This won't overwrite the
  371. // unsearched region of the string so long as |write_offset| <= |read_offset|;
  372. // that condition is always satisfied because:
  373. //
  374. // (a) If the string is being shortened, |expansion| is zero and
  375. // |write_offset| grows slower than |read_offset|.
  376. //
  377. // (b) If the string is being lengthened, |write_offset| grows faster than
  378. // |read_offset|, but |expansion| is big enough so that |write_offset|
  379. // will only catch up to |read_offset| at the point of the last match.
  380. auto* buffer = &((*str)[0]);
  381. size_t write_offset = first_match;
  382. size_t read_offset = first_match + expansion;
  383. do {
  384. if (replace_length) {
  385. CharTraits::copy(buffer + write_offset, replace_with.data(),
  386. replace_length);
  387. write_offset += replace_length;
  388. }
  389. read_offset += find_length;
  390. // min() clamps std::basic_string<CharT>::npos (the largest unsigned value)
  391. // to str_length.
  392. size_t match = std::min(matcher.Find(*str, read_offset), str_length);
  393. size_t length = match - read_offset;
  394. if (length) {
  395. CharTraits::move(buffer + write_offset, buffer + read_offset, length);
  396. write_offset += length;
  397. read_offset += length;
  398. }
  399. } while (read_offset < str_length);
  400. // If we're shortening the string, truncate it now.
  401. str->resize(write_offset);
  402. return true;
  403. }
  404. template <typename T, typename CharT = typename T::value_type>
  405. bool ReplaceCharsT(T input,
  406. T find_any_of_these,
  407. T replace_with,
  408. std::basic_string<CharT>* output) {
  409. // Commonly, this is called with output and input being the same string; in
  410. // that case, skip the copy.
  411. if (input.data() != output->data() || input.size() != output->size())
  412. output->assign(input.data(), input.size());
  413. return DoReplaceMatchesAfterOffset(output, 0,
  414. MakeCharacterMatcher(find_any_of_these),
  415. replace_with, ReplaceType::REPLACE_ALL);
  416. }
  417. template <class string_type>
  418. inline typename string_type::value_type* WriteIntoT(string_type* str,
  419. size_t length_with_null) {
  420. DCHECK_GE(length_with_null, 1u);
  421. str->reserve(length_with_null);
  422. str->resize(length_with_null - 1);
  423. return &((*str)[0]);
  424. }
  425. // Generic version for all JoinString overloads. |list_type| must be a sequence
  426. // (base::span or std::initializer_list) of strings/StringPieces (std::string,
  427. // std::u16string, StringPiece or StringPiece16). |CharT| is either char or
  428. // char16_t.
  429. template <typename list_type,
  430. typename T,
  431. typename CharT = typename T::value_type>
  432. static std::basic_string<CharT> JoinStringT(list_type parts, T sep) {
  433. if (std::empty(parts))
  434. return std::basic_string<CharT>();
  435. // Pre-allocate the eventual size of the string. Start with the size of all of
  436. // the separators (note that this *assumes* parts.size() > 0).
  437. size_t total_size = (parts.size() - 1) * sep.size();
  438. for (const auto& part : parts)
  439. total_size += part.size();
  440. std::basic_string<CharT> result;
  441. result.reserve(total_size);
  442. auto iter = parts.begin();
  443. DCHECK(iter != parts.end());
  444. result.append(iter->data(), iter->size());
  445. ++iter;
  446. for (; iter != parts.end(); ++iter) {
  447. result.append(sep.data(), sep.size());
  448. result.append(iter->data(), iter->size());
  449. }
  450. // Sanity-check that we pre-allocated correctly.
  451. DCHECK_EQ(total_size, result.size());
  452. return result;
  453. }
  454. template <typename T, typename CharT = typename T::value_type>
  455. std::basic_string<CharT> DoReplaceStringPlaceholders(
  456. T format_string,
  457. const std::vector<std::basic_string<CharT>>& subst,
  458. std::vector<size_t>* offsets) {
  459. size_t substitutions = subst.size();
  460. DCHECK_LT(substitutions, 11U);
  461. size_t sub_length = 0;
  462. for (const auto& cur : subst)
  463. sub_length += cur.length();
  464. std::basic_string<CharT> formatted;
  465. formatted.reserve(format_string.length() + sub_length);
  466. std::vector<ReplacementOffset> r_offsets;
  467. for (auto i = format_string.begin(); i != format_string.end(); ++i) {
  468. if ('$' == *i) {
  469. if (i + 1 != format_string.end()) {
  470. ++i;
  471. if ('$' == *i) {
  472. while (i != format_string.end() && '$' == *i) {
  473. formatted.push_back('$');
  474. ++i;
  475. }
  476. --i;
  477. } else {
  478. if (*i < '1' || *i > '9') {
  479. DLOG(ERROR) << "Invalid placeholder: $"
  480. << std::basic_string<CharT>(1, *i);
  481. continue;
  482. }
  483. size_t index = static_cast<size_t>(*i - '1');
  484. if (offsets) {
  485. ReplacementOffset r_offset(index, formatted.size());
  486. r_offsets.insert(
  487. ranges::upper_bound(r_offsets, r_offset, &CompareParameter),
  488. r_offset);
  489. }
  490. if (index < substitutions)
  491. formatted.append(subst.at(index));
  492. }
  493. }
  494. } else {
  495. formatted.push_back(*i);
  496. }
  497. }
  498. if (offsets) {
  499. for (const auto& cur : r_offsets)
  500. offsets->push_back(cur.offset);
  501. }
  502. return formatted;
  503. }
  504. // The following code is compatible with the OpenBSD lcpy interface. See:
  505. // http://www.gratisoft.us/todd/papers/strlcpy.html
  506. // ftp://ftp.openbsd.org/pub/OpenBSD/src/lib/libc/string/{wcs,str}lcpy.c
  507. template <typename CHAR>
  508. size_t lcpyT(CHAR* dst, const CHAR* src, size_t dst_size) {
  509. for (size_t i = 0; i < dst_size; ++i) {
  510. if ((dst[i] = src[i]) == 0) // We hit and copied the terminating NULL.
  511. return i;
  512. }
  513. // We were left off at dst_size. We over copied 1 byte. Null terminate.
  514. if (dst_size != 0)
  515. dst[dst_size - 1] = 0;
  516. // Count the rest of the |src|, and return it's length in characters.
  517. while (src[dst_size])
  518. ++dst_size;
  519. return dst_size;
  520. }
  521. } // namespace internal
  522. } // namespace base
  523. #endif // BASE_STRINGS_STRING_UTIL_INTERNAL_H_