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