diff options
Diffstat (limited to 'absl/strings/str_replace.h')
| -rw-r--r-- | absl/strings/str_replace.h | 213 |
1 files changed, 213 insertions, 0 deletions
diff --git a/absl/strings/str_replace.h b/absl/strings/str_replace.h new file mode 100644 index 000000000000..f4d9bb9545d6 --- /dev/null +++ b/absl/strings/str_replace.h @@ -0,0 +1,213 @@ +// +// 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 +// +// http://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 std::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 std::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 { + +// StrReplaceAll() +// +// Replaces character sequences within a given std::string with replacements provided +// within an initializer list of key/value pairs. Candidate replacements are +// considered in order as they occur within the std::string, with earlier matches +// taking precedence, and longer matches taking precedence for candidates +// starting at the same position in the std::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 std::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 +// std::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; +} + +} // namespace absl + +#endif // ABSL_STRINGS_STR_REPLACE_H_ |