legacy-libs/grpc/deps/grpc/third_party/abseil-cpp/absl/strings/str_replace.h

   1 //
   2 // Copyright 2017 The Abseil Authors.
   3 //
   4 // Licensed under the Apache License, Version 2.0 (the "License");
   5 // you may not use this file except in compliance with the License.
   6 // You may obtain a copy of the License at
   7 //
   8 //      https://www.apache.org/licenses/LICENSE-2.0
   9 //
  10 // Unless required by applicable law or agreed to in writing, software
  11 // distributed under the License is distributed on an "AS IS" BASIS,
  12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 // See the License for the specific language governing permissions and
  14 // limitations under the License.
  15 //
  16 // -----------------------------------------------------------------------------
  17 // File: str_replace.h
  18 // -----------------------------------------------------------------------------
  19 //
  20 // This file defines `absl::StrReplaceAll()`, a general-purpose string
  21 // replacement function designed for large, arbitrary text substitutions,
  22 // especially on strings which you are receiving from some other system for
  23 // further processing (e.g. processing regular expressions, escaping HTML
  24 // entities, etc.). `StrReplaceAll` is designed to be efficient even when only
  25 // one substitution is being performed, or when substitution is rare.
  26 //
  27 // If the string being modified is known at compile-time, and the substitutions
  28 // vary, `absl::Substitute()` may be a better choice.
  29 //
  30 // Example:
  31 //
  32 // std::string html_escaped = absl::StrReplaceAll(user_input, {
  33 //                                                {"&", "&amp;"},
  34 //                                                {"<", "&lt;"},
  35 //                                                {">", "&gt;"},
  36 //                                                {"\"", "&quot;"},
  37 //                                                {"'", "&#39;"}});
  38 #ifndef ABSL_STRINGS_STR_REPLACE_H_
  39 #define ABSL_STRINGS_STR_REPLACE_H_
  40
  41 #include <string>
  42 #include <utility>
  43 #include <vector>
  44
  45 #include "absl/base/attributes.h"
  46 #include "absl/strings/string_view.h"
  47
  48 namespace absl {
  49
  50 // StrReplaceAll()
  51 //
  52 // Replaces character sequences within a given string with replacements provided
  53 // within an initializer list of key/value pairs. Candidate replacements are
  54 // considered in order as they occur within the string, with earlier matches
  55 // taking precedence, and longer matches taking precedence for candidates
  56 // starting at the same position in the string. Once a substitution is made, the
  57 // replaced text is not considered for any further substitutions.
  58 //
  59 // Example:
  60 //
  61 //   std::string s = absl::StrReplaceAll(
  62 //       "$who bought $count #Noun. Thanks $who!",
  63 //       {{"$count", absl::StrCat(5)},
  64 //        {"$who", "Bob"},
  65 //        {"#Noun", "Apples"}});
  66 //   EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s);
  67 ABSL_MUST_USE_RESULT std::string StrReplaceAll(
  68     absl::string_view s,
  69     std::initializer_list<std::pair<absl::string_view, absl::string_view>>
  70         replacements);
  71
  72 // Overload of `StrReplaceAll()` to accept a container of key/value replacement
  73 // pairs (typically either an associative map or a `std::vector` of `std::pair`
  74 // elements). A vector of pairs is generally more efficient.
  75 //
  76 // Examples:
  77 //
  78 //   std::map<const absl::string_view, const absl::string_view> replacements;
  79 //   replacements["$who"] = "Bob";
  80 //   replacements["$count"] = "5";
  81 //   replacements["#Noun"] = "Apples";
  82 //   std::string s = absl::StrReplaceAll(
  83 //       "$who bought $count #Noun. Thanks $who!",
  84 //       replacements);
  85 //   EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s);
  86 //
  87 //   // A std::vector of std::pair elements can be more efficient.
  88 //   std::vector<std::pair<const absl::string_view, std::string>> replacements;
  89 //   replacements.push_back({"&", "&amp;"});
  90 //   replacements.push_back({"<", "&lt;"});
  91 //   replacements.push_back({">", "&gt;"});
  92 //   std::string s = absl::StrReplaceAll("if (ptr < &foo)",
  93 //                                  replacements);
  94 //   EXPECT_EQ("if (ptr &lt; &amp;foo)", s);
  95 template <typename StrToStrMapping>
  96 std::string StrReplaceAll(absl::string_view s,
  97                           const StrToStrMapping& replacements);
  98
  99 // Overload of `StrReplaceAll()` to replace character sequences within a given
 100 // output string *in place* with replacements provided within an initializer
 101 // list of key/value pairs, returning the number of substitutions that occurred.
 102 //
 103 // Example:
 104 //
 105 //   std::string s = std::string("$who bought $count #Noun. Thanks $who!");
 106 //   int count;
 107 //   count = absl::StrReplaceAll({{"$count", absl::StrCat(5)},
 108 //                               {"$who", "Bob"},
 109 //                               {"#Noun", "Apples"}}, &s);
 110 //  EXPECT_EQ(count, 4);
 111 //  EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s);
 112 int StrReplaceAll(
 113     std::initializer_list<std::pair<absl::string_view, absl::string_view>>
 114         replacements,
 115     std::string* target);
 116
 117 // Overload of `StrReplaceAll()` to replace patterns within a given output
 118 // string *in place* with replacements provided within a container of key/value
 119 // pairs.
 120 //
 121 // Example:
 122 //
 123 //   std::string s = std::string("if (ptr < &foo)");
 124 //   int count = absl::StrReplaceAll({{"&", "&amp;"},
 125 //                                    {"<", "&lt;"},
 126 //                                    {">", "&gt;"}}, &s);
 127 //  EXPECT_EQ(count, 2);
 128 //  EXPECT_EQ("if (ptr &lt; &amp;foo)", s);
 129 template <typename StrToStrMapping>
 130 int StrReplaceAll(const StrToStrMapping& replacements, std::string* target);
 131
 132 // Implementation details only, past this point.
 133 namespace strings_internal {
 134
 135 struct ViableSubstitution {
 136   absl::string_view old;
 137   absl::string_view replacement;
 138   size_t offset;
 139
 140   ViableSubstitution(absl::string_view old_str,
 141                      absl::string_view replacement_str, size_t offset_val)
 142       : old(old_str), replacement(replacement_str), offset(offset_val) {}
 143
 144   // One substitution occurs "before" another (takes priority) if either
 145   // it has the lowest offset, or it has the same offset but a larger size.
 146   bool OccursBefore(const ViableSubstitution& y) const {
 147     if (offset != y.offset) return offset < y.offset;
 148     return old.size() > y.old.size();
 149   }
 150 };
 151
 152 // Build a vector of ViableSubstitutions based on the given list of
 153 // replacements. subs can be implemented as a priority_queue. However, it turns
 154 // out that most callers have small enough a list of substitutions that the
 155 // overhead of such a queue isn't worth it.
 156 template <typename StrToStrMapping>
 157 std::vector<ViableSubstitution> FindSubstitutions(
 158     absl::string_view s, const StrToStrMapping& replacements) {
 159   std::vector<ViableSubstitution> subs;
 160   subs.reserve(replacements.size());
 161
 162   for (const auto& rep : replacements) {
 163     using std::get;
 164     absl::string_view old(get<0>(rep));
 165
 166     size_t pos = s.find(old);
 167     if (pos == s.npos) continue;
 168
 169     // Ignore attempts to replace "". This condition is almost never true,
 170     // but above condition is frequently true. That's why we test for this
 171     // now and not before.
 172     if (old.empty()) continue;
 173
 174     subs.emplace_back(old, get<1>(rep), pos);
 175
 176     // Insertion sort to ensure the last ViableSubstitution comes before
 177     // all the others.
 178     size_t index = subs.size();
 179     while (--index && subs[index - 1].OccursBefore(subs[index])) {
 180       std::swap(subs[index], subs[index - 1]);
 181     }
 182   }
 183   return subs;
 184 }
 185
 186 int ApplySubstitutions(absl::string_view s,
 187                        std::vector<ViableSubstitution>* subs_ptr,
 188                        std::string* result_ptr);
 189
 190 }  // namespace strings_internal
 191
 192 template <typename StrToStrMapping>
 193 std::string StrReplaceAll(absl::string_view s,
 194                           const StrToStrMapping& replacements) {
 195   auto subs = strings_internal::FindSubstitutions(s, replacements);
 196   std::string result;
 197   result.reserve(s.size());
 198   strings_internal::ApplySubstitutions(s, &subs, &result);
 199   return result;
 200 }
 201
 202 template <typename StrToStrMapping>
 203 int StrReplaceAll(const StrToStrMapping& replacements, std::string* target) {
 204   auto subs = strings_internal::FindSubstitutions(*target, replacements);
 205   if (subs.empty()) return 0;
 206
 207   std::string result;
 208   result.reserve(target->size());
 209   int substitutions =
 210       strings_internal::ApplySubstitutions(*target, &subs, &result);
 211   target->swap(result);
 212   return substitutions;
 213 }
 214
 215 }  // namespace absl
 216
 217 #endif  // ABSL_STRINGS_STR_REPLACE_H_