str_replace.h (8507B)
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 // {"&", "&"}, 34 // {"<", "<"}, 35 // {">", ">"}, 36 // {"\"", """}, 37 // {"'", "'"}}); 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/base/nullability.h" 47 #include "absl/strings/string_view.h" 48 49 namespace absl { 50 ABSL_NAMESPACE_BEGIN 51 52 // StrReplaceAll() 53 // 54 // Replaces character sequences within a given string with replacements provided 55 // within an initializer list of key/value pairs. Candidate replacements are 56 // considered in order as they occur within the string, with earlier matches 57 // taking precedence, and longer matches taking precedence for candidates 58 // starting at the same position in the string. Once a substitution is made, the 59 // replaced text is not considered for any further substitutions. 60 // 61 // Example: 62 // 63 // std::string s = absl::StrReplaceAll( 64 // "$who bought $count #Noun. Thanks $who!", 65 // {{"$count", absl::StrCat(5)}, 66 // {"$who", "Bob"}, 67 // {"#Noun", "Apples"}}); 68 // EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s); 69 [[nodiscard]] std::string StrReplaceAll( 70 absl::string_view s, 71 std::initializer_list<std::pair<absl::string_view, absl::string_view>> 72 replacements); 73 74 // Overload of `StrReplaceAll()` to accept a container of key/value replacement 75 // pairs (typically either an associative map or a `std::vector` of `std::pair` 76 // elements). A vector of pairs is generally more efficient. 77 // 78 // Examples: 79 // 80 // std::map<const absl::string_view, const absl::string_view> replacements; 81 // replacements["$who"] = "Bob"; 82 // replacements["$count"] = "5"; 83 // replacements["#Noun"] = "Apples"; 84 // std::string s = absl::StrReplaceAll( 85 // "$who bought $count #Noun. Thanks $who!", 86 // replacements); 87 // EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s); 88 // 89 // // A std::vector of std::pair elements can be more efficient. 90 // std::vector<std::pair<const absl::string_view, std::string>> replacements; 91 // replacements.push_back({"&", "&"}); 92 // replacements.push_back({"<", "<"}); 93 // replacements.push_back({">", ">"}); 94 // std::string s = absl::StrReplaceAll("if (ptr < &foo)", 95 // replacements); 96 // EXPECT_EQ("if (ptr < &foo)", s); 97 template <typename StrToStrMapping> 98 std::string StrReplaceAll(absl::string_view s, 99 const StrToStrMapping& replacements); 100 101 // Overload of `StrReplaceAll()` to replace character sequences within a given 102 // output string *in place* with replacements provided within an initializer 103 // list of key/value pairs, returning the number of substitutions that occurred. 104 // 105 // Example: 106 // 107 // std::string s = std::string("$who bought $count #Noun. Thanks $who!"); 108 // int count; 109 // count = absl::StrReplaceAll({{"$count", absl::StrCat(5)}, 110 // {"$who", "Bob"}, 111 // {"#Noun", "Apples"}}, &s); 112 // EXPECT_EQ(count, 4); 113 // EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s); 114 int StrReplaceAll( 115 std::initializer_list<std::pair<absl::string_view, absl::string_view>> 116 replacements, 117 absl::Nonnull<std::string*> target); 118 119 // Overload of `StrReplaceAll()` to replace patterns within a given output 120 // string *in place* with replacements provided within a container of key/value 121 // pairs. 122 // 123 // Example: 124 // 125 // std::string s = std::string("if (ptr < &foo)"); 126 // int count = absl::StrReplaceAll({{"&", "&"}, 127 // {"<", "<"}, 128 // {">", ">"}}, &s); 129 // EXPECT_EQ(count, 2); 130 // EXPECT_EQ("if (ptr < &foo)", s); 131 template <typename StrToStrMapping> 132 int StrReplaceAll(const StrToStrMapping& replacements, 133 absl::Nonnull<std::string*> target); 134 135 // Implementation details only, past this point. 136 namespace strings_internal { 137 138 struct ViableSubstitution { 139 absl::string_view old; 140 absl::string_view replacement; 141 size_t offset; 142 143 ViableSubstitution(absl::string_view old_str, 144 absl::string_view replacement_str, size_t offset_val) 145 : old(old_str), replacement(replacement_str), offset(offset_val) {} 146 147 // One substitution occurs "before" another (takes priority) if either 148 // it has the lowest offset, or it has the same offset but a larger size. 149 bool OccursBefore(const ViableSubstitution& y) const { 150 if (offset != y.offset) return offset < y.offset; 151 return old.size() > y.old.size(); 152 } 153 }; 154 155 // Build a vector of ViableSubstitutions based on the given list of 156 // replacements. subs can be implemented as a priority_queue. However, it turns 157 // out that most callers have small enough a list of substitutions that the 158 // overhead of such a queue isn't worth it. 159 template <typename StrToStrMapping> 160 std::vector<ViableSubstitution> FindSubstitutions( 161 absl::string_view s, const StrToStrMapping& replacements) { 162 std::vector<ViableSubstitution> subs; 163 subs.reserve(replacements.size()); 164 165 for (const auto& rep : replacements) { 166 using std::get; 167 absl::string_view old(get<0>(rep)); 168 169 size_t pos = s.find(old); 170 if (pos == s.npos) continue; 171 172 // Ignore attempts to replace "". This condition is almost never true, 173 // but above condition is frequently true. That's why we test for this 174 // now and not before. 175 if (old.empty()) continue; 176 177 subs.emplace_back(old, get<1>(rep), pos); 178 179 // Insertion sort to ensure the last ViableSubstitution comes before 180 // all the others. 181 size_t index = subs.size(); 182 while (--index && subs[index - 1].OccursBefore(subs[index])) { 183 std::swap(subs[index], subs[index - 1]); 184 } 185 } 186 return subs; 187 } 188 189 int ApplySubstitutions(absl::string_view s, 190 absl::Nonnull<std::vector<ViableSubstitution>*> subs_ptr, 191 absl::Nonnull<std::string*> result_ptr); 192 193 } // namespace strings_internal 194 195 template <typename StrToStrMapping> 196 std::string StrReplaceAll(absl::string_view s, 197 const StrToStrMapping& replacements) { 198 auto subs = strings_internal::FindSubstitutions(s, replacements); 199 std::string result; 200 result.reserve(s.size()); 201 strings_internal::ApplySubstitutions(s, &subs, &result); 202 return result; 203 } 204 205 template <typename StrToStrMapping> 206 int StrReplaceAll(const StrToStrMapping& replacements, 207 absl::Nonnull<std::string*> target) { 208 auto subs = strings_internal::FindSubstitutions(*target, replacements); 209 if (subs.empty()) return 0; 210 211 std::string result; 212 result.reserve(target->size()); 213 int substitutions = 214 strings_internal::ApplySubstitutions(*target, &subs, &result); 215 target->swap(result); 216 return substitutions; 217 } 218 219 ABSL_NAMESPACE_END 220 } // namespace absl 221 222 #endif // ABSL_STRINGS_STR_REPLACE_H_