// // Copyright 2017 The Abseil Authors. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // https://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. // // ----------------------------------------------------------------------------- // File: str_replace.h // ----------------------------------------------------------------------------- // // This file defines `absl::StrReplaceAll()`, a general-purpose string // replacement function designed for large, arbitrary text substitutions, // especially on strings which you are receiving from some other system for // further processing (e.g. processing regular expressions, escaping HTML // entities, etc.). `StrReplaceAll` is designed to be efficient even when only // one substitution is being performed, or when substitution is rare. // // If the string being modified is known at compile-time, and the substitutions // vary, `absl::Substitute()` may be a better choice. // // Example: // // std::string html_escaped = absl::StrReplaceAll(user_input, { // {"&", "&"}, // {"<", "<"}, // {">", ">"}, // {"\"", """}, // {"'", "'"}}); #ifndef ABSL_STRINGS_STR_REPLACE_H_ #define ABSL_STRINGS_STR_REPLACE_H_ #include <string> #include <utility> #include <vector> #include "absl/base/attributes.h" #include "absl/strings/string_view.h" namespace absl { ABSL_NAMESPACE_BEGIN // StrReplaceAll() // // Replaces character sequences within a given string with replacements provided // within an initializer list of key/value pairs. Candidate replacements are // considered in order as they occur within the string, with earlier matches // taking precedence, and longer matches taking precedence for candidates // starting at the same position in the string. Once a substitution is made, the // replaced text is not considered for any further substitutions. // // Example: // // std::string s = absl::StrReplaceAll( // "$who bought $count #Noun. Thanks $who!", // {{"$count", absl::StrCat(5)}, // {"$who", "Bob"}, // {"#Noun", "Apples"}}); // EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s); ABSL_MUST_USE_RESULT std::string StrReplaceAll( absl::string_view s, std::initializer_list<std::pair<absl::string_view, absl::string_view>> replacements); // Overload of `StrReplaceAll()` to accept a container of key/value replacement // pairs (typically either an associative map or a `std::vector` of `std::pair` // elements). A vector of pairs is generally more efficient. // // Examples: // // std::map<const absl::string_view, const absl::string_view> replacements; // replacements["$who"] = "Bob"; // replacements["$count"] = "5"; // replacements["#Noun"] = "Apples"; // std::string s = absl::StrReplaceAll( // "$who bought $count #Noun. Thanks $who!", // replacements); // EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s); // // // A std::vector of std::pair elements can be more efficient. // std::vector<std::pair<const absl::string_view, std::string>> replacements; // replacements.push_back({"&", "&"}); // replacements.push_back({"<", "<"}); // replacements.push_back({">", ">"}); // std::string s = absl::StrReplaceAll("if (ptr < &foo)", // replacements); // EXPECT_EQ("if (ptr < &foo)", s); template <typename StrToStrMapping> std::string StrReplaceAll(absl::string_view s, const StrToStrMapping& replacements); // Overload of `StrReplaceAll()` to replace character sequences within a given // output string *in place* with replacements provided within an initializer // list of key/value pairs, returning the number of substitutions that occurred. // // Example: // // std::string s = std::string("$who bought $count #Noun. Thanks $who!"); // int count; // count = absl::StrReplaceAll({{"$count", absl::StrCat(5)}, // {"$who", "Bob"}, // {"#Noun", "Apples"}}, &s); // EXPECT_EQ(count, 4); // EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s); int StrReplaceAll( std::initializer_list<std::pair<absl::string_view, absl::string_view>> replacements, std::string* target); // Overload of `StrReplaceAll()` to replace patterns within a given output // string *in place* with replacements provided within a container of key/value // pairs. // // Example: // // std::string s = std::string("if (ptr < &foo)"); // int count = absl::StrReplaceAll({{"&", "&"}, // {"<", "<"}, // {">", ">"}}, &s); // EXPECT_EQ(count, 2); // EXPECT_EQ("if (ptr < &foo)", s); template <typename StrToStrMapping> int StrReplaceAll(const StrToStrMapping& replacements, std::string* target); // Implementation details only, past this point. namespace strings_internal { struct ViableSubstitution { absl::string_view old; absl::string_view replacement; size_t offset; ViableSubstitution(absl::string_view old_str, absl::string_view replacement_str, size_t offset_val) : old(old_str), replacement(replacement_str), offset(offset_val) {} // One substitution occurs "before" another (takes priority) if either // it has the lowest offset, or it has the same offset but a larger size. bool OccursBefore(const ViableSubstitution& y) const { if (offset != y.offset) return offset < y.offset; return old.size() > y.old.size(); } }; // Build a vector of ViableSubstitutions based on the given list of // replacements. subs can be implemented as a priority_queue. However, it turns // out that most callers have small enough a list of substitutions that the // overhead of such a queue isn't worth it. template <typename StrToStrMapping> std::vector<ViableSubstitution> FindSubstitutions( absl::string_view s, const StrToStrMapping& replacements) { std::vector<ViableSubstitution> subs; subs.reserve(replacements.size()); for (const auto& rep : replacements) { using std::get; absl::string_view old(get<0>(rep)); size_t pos = s.find(old); if (pos == s.npos) continue; // Ignore attempts to replace "". This condition is almost never true, // but above condition is frequently true. That's why we test for this // now and not before. if (old.empty()) continue; subs.emplace_back(old, get<1>(rep), pos); // Insertion sort to ensure the last ViableSubstitution comes before // all the others. size_t index = subs.size(); while (--index && subs[index - 1].OccursBefore(subs[index])) { std::swap(subs[index], subs[index - 1]); } } return subs; } int ApplySubstitutions(absl::string_view s, std::vector<ViableSubstitution>* subs_ptr, std::string* result_ptr); } // namespace strings_internal template <typename StrToStrMapping> std::string StrReplaceAll(absl::string_view s, const StrToStrMapping& replacements) { auto subs = strings_internal::FindSubstitutions(s, replacements); std::string result; result.reserve(s.size()); strings_internal::ApplySubstitutions(s, &subs, &result); return result; } template <typename StrToStrMapping> int StrReplaceAll(const StrToStrMapping& replacements, std::string* target) { auto subs = strings_internal::FindSubstitutions(*target, replacements); if (subs.empty()) return 0; std::string result; result.reserve(target->size()); int substitutions = strings_internal::ApplySubstitutions(*target, &subs, &result); target->swap(result); return substitutions; } ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_STRINGS_STR_REPLACE_H_