str_replace.h
Go to the documentation of this file.
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"
47 
48 namespace 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);
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);
95 template <typename StrToStrMapping>
96 std::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);
112 int 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);
129 template <typename StrToStrMapping>
130 int StrReplaceAll(const StrToStrMapping& replacements, std::string* target);
131 
132 // Implementation details only, past this point.
133 namespace strings_internal {
134 
138  size_t offset;
139 
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.
156 template <typename StrToStrMapping>
157 std::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 
187  std::vector<ViableSubstitution>* subs_ptr,
188  std::string* result_ptr);
189 
190 } // namespace strings_internal
191 
192 template <typename StrToStrMapping>
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 
202 template <typename StrToStrMapping>
203 int 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_
size_type find(string_view s, size_type pos=0) const noexcept
Definition: string_view.cc:92
static constexpr size_type npos
Definition: string_view.h:159
std::vector< ViableSubstitution > FindSubstitutions(absl::string_view s, const StrToStrMapping &replacements)
Definition: str_replace.h:157
Definition: algorithm.h:29
constexpr size_type size() const noexcept
Definition: string_view.h:260
bool OccursBefore(const ViableSubstitution &y) const
Definition: str_replace.h:146
ViableSubstitution(absl::string_view old_str, absl::string_view replacement_str, size_t offset_val)
Definition: str_replace.h:140
#define ABSL_MUST_USE_RESULT
Definition: attributes.h:449
void swap(absl::InlinedVector< T, N, A > &a, absl::InlinedVector< T, N, A > &b) noexcept(noexcept(a.swap(b)))
constexpr bool empty() const noexcept
Definition: string_view.h:277
absl::string_view get(const Cont &c)
int ApplySubstitutions(absl::string_view s, std::vector< strings_internal::ViableSubstitution > *subs_ptr, std::string *result_ptr)
Definition: str_replace.cc:28
std::string StrReplaceAll(absl::string_view s, strings_internal::FixedMapping replacements)
Definition: str_replace.cc:70


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:19:58