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// {"<", "&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
48namespace 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);
67ABSL_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);
95template <typename StrToStrMapping>
96std::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);
112int 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);
129template <typename StrToStrMapping>
130int StrReplaceAll(const StrToStrMapping& replacements, std::string* target);
131
132// Implementation details only, past this point.
133namespace strings_internal {
134
135struct 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.
156template <typename StrToStrMapping>
157std::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
186int ApplySubstitutions(absl::string_view s,
187 std::vector<ViableSubstitution>* subs_ptr,
188 std::string* result_ptr);
189
190} // namespace strings_internal
191
192template <typename StrToStrMapping>
193std::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
202template <typename StrToStrMapping>
203int 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_
218