str_join_internal.h (11224B)
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 // This file declares INTERNAL parts of the Join API that are inlined/templated 18 // or otherwise need to be available at compile time. The main abstractions 19 // defined in this file are: 20 // 21 // - A handful of default Formatters 22 // - JoinAlgorithm() overloads 23 // - JoinRange() overloads 24 // - JoinTuple() 25 // 26 // DO NOT INCLUDE THIS FILE DIRECTLY. Use this file by including 27 // absl/strings/str_join.h 28 // 29 // IWYU pragma: private, include "absl/strings/str_join.h" 30 31 #ifndef ABSL_STRINGS_INTERNAL_STR_JOIN_INTERNAL_H_ 32 #define ABSL_STRINGS_INTERNAL_STR_JOIN_INTERNAL_H_ 33 34 #include <cstdint> 35 #include <cstring> 36 #include <initializer_list> 37 #include <iterator> 38 #include <limits> 39 #include <memory> 40 #include <string> 41 #include <tuple> 42 #include <type_traits> 43 #include <utility> 44 45 #include "absl/base/config.h" 46 #include "absl/base/internal/iterator_traits.h" 47 #include "absl/base/internal/raw_logging.h" 48 #include "absl/strings/internal/ostringstream.h" 49 #include "absl/strings/internal/resize_uninitialized.h" 50 #include "absl/strings/str_cat.h" 51 #include "absl/strings/string_view.h" 52 53 namespace absl { 54 ABSL_NAMESPACE_BEGIN 55 namespace strings_internal { 56 57 // 58 // Formatter objects 59 // 60 // The following are implementation classes for standard Formatter objects. The 61 // factory functions that users will call to create and use these formatters are 62 // defined and documented in strings/join.h. 63 // 64 65 // The default formatter. Converts alpha-numeric types to strings. 66 struct AlphaNumFormatterImpl { 67 // This template is needed in order to support passing in a dereferenced 68 // vector<bool>::iterator 69 template <typename T> 70 void operator()(std::string* out, const T& t) const { 71 StrAppend(out, AlphaNum(t)); 72 } 73 74 void operator()(std::string* out, const AlphaNum& t) const { 75 StrAppend(out, t); 76 } 77 }; 78 79 // A type that's used to overload the JoinAlgorithm() function (defined below) 80 // for ranges that do not require additional formatting (e.g., a range of 81 // strings). 82 83 struct NoFormatter : public AlphaNumFormatterImpl {}; 84 85 // Formats types to strings using the << operator. 86 class StreamFormatterImpl { 87 public: 88 // The method isn't const because it mutates state. Making it const will 89 // render StreamFormatterImpl thread-hostile. 90 template <typename T> 91 void operator()(std::string* out, const T& t) { 92 // The stream is created lazily to avoid paying the relatively high cost 93 // of its construction when joining an empty range. 94 if (strm_) { 95 strm_->clear(); // clear the bad, fail and eof bits in case they were set 96 strm_->str(out); 97 } else { 98 strm_.reset(new strings_internal::OStringStream(out)); 99 } 100 *strm_ << t; 101 } 102 103 private: 104 std::unique_ptr<strings_internal::OStringStream> strm_; 105 }; 106 107 // Formats a std::pair<>. The 'first' member is formatted using f1_ and the 108 // 'second' member is formatted using f2_. sep_ is the separator. 109 template <typename F1, typename F2> 110 class PairFormatterImpl { 111 public: 112 PairFormatterImpl(F1 f1, absl::string_view sep, F2 f2) 113 : f1_(std::move(f1)), sep_(sep), f2_(std::move(f2)) {} 114 115 template <typename T> 116 void operator()(std::string* out, const T& p) { 117 f1_(out, p.first); 118 out->append(sep_); 119 f2_(out, p.second); 120 } 121 122 template <typename T> 123 void operator()(std::string* out, const T& p) const { 124 f1_(out, p.first); 125 out->append(sep_); 126 f2_(out, p.second); 127 } 128 129 private: 130 F1 f1_; 131 std::string sep_; 132 F2 f2_; 133 }; 134 135 // Wraps another formatter and dereferences the argument to operator() then 136 // passes the dereferenced argument to the wrapped formatter. This can be 137 // useful, for example, to join a std::vector<int*>. 138 template <typename Formatter> 139 class DereferenceFormatterImpl { 140 public: 141 DereferenceFormatterImpl() : f_() {} 142 explicit DereferenceFormatterImpl(Formatter&& f) 143 : f_(std::forward<Formatter>(f)) {} 144 145 template <typename T> 146 void operator()(std::string* out, const T& t) { 147 f_(out, *t); 148 } 149 150 template <typename T> 151 void operator()(std::string* out, const T& t) const { 152 f_(out, *t); 153 } 154 155 private: 156 Formatter f_; 157 }; 158 159 // DefaultFormatter<T> is a traits class that selects a default Formatter to use 160 // for the given type T. The ::Type member names the Formatter to use. This is 161 // used by the strings::Join() functions that do NOT take a Formatter argument, 162 // in which case a default Formatter must be chosen. 163 // 164 // AlphaNumFormatterImpl is the default in the base template, followed by 165 // specializations for other types. 166 template <typename ValueType> 167 struct DefaultFormatter { 168 typedef AlphaNumFormatterImpl Type; 169 }; 170 template <> 171 struct DefaultFormatter<const char*> { 172 typedef AlphaNumFormatterImpl Type; 173 }; 174 template <> 175 struct DefaultFormatter<char*> { 176 typedef AlphaNumFormatterImpl Type; 177 }; 178 template <> 179 struct DefaultFormatter<std::string> { 180 typedef NoFormatter Type; 181 }; 182 template <> 183 struct DefaultFormatter<absl::string_view> { 184 typedef NoFormatter Type; 185 }; 186 template <typename ValueType> 187 struct DefaultFormatter<ValueType*> { 188 typedef DereferenceFormatterImpl<typename DefaultFormatter<ValueType>::Type> 189 Type; 190 }; 191 192 template <typename ValueType> 193 struct DefaultFormatter<std::unique_ptr<ValueType>> 194 : public DefaultFormatter<ValueType*> {}; 195 196 // 197 // JoinAlgorithm() functions 198 // 199 200 // The main joining algorithm. This simply joins the elements in the given 201 // iterator range, each separated by the given separator, into an output string, 202 // and formats each element using the provided Formatter object. 203 template <typename Iterator, typename Formatter> 204 std::string JoinAlgorithm(Iterator start, Iterator end, absl::string_view s, 205 Formatter&& f) { 206 std::string result; 207 absl::string_view sep(""); 208 for (Iterator it = start; it != end; ++it) { 209 result.append(sep.data(), sep.size()); 210 f(&result, *it); 211 sep = s; 212 } 213 return result; 214 } 215 216 // A joining algorithm that's optimized for a forward iterator range of 217 // string-like objects that do not need any additional formatting. This is to 218 // optimize the common case of joining, say, a std::vector<string> or a 219 // std::vector<absl::string_view>. 220 // 221 // This is an overload of the previous JoinAlgorithm() function. Here the 222 // Formatter argument is of type NoFormatter. Since NoFormatter is an internal 223 // type, this overload is only invoked when strings::Join() is called with a 224 // range of string-like objects (e.g., std::string, absl::string_view), and an 225 // explicit Formatter argument was NOT specified. 226 // 227 // The optimization is that the needed space will be reserved in the output 228 // string to avoid the need to resize while appending. To do this, the iterator 229 // range will be traversed twice: once to calculate the total needed size, and 230 // then again to copy the elements and delimiters to the output string. 231 template <typename Iterator, 232 typename = std::enable_if_t< 233 base_internal::IsAtLeastForwardIterator<Iterator>::value>> 234 std::string JoinAlgorithm(Iterator start, Iterator end, absl::string_view s, 235 NoFormatter) { 236 std::string result; 237 if (start != end) { 238 // Sums size 239 auto&& start_value = *start; 240 // Use uint64_t to prevent size_t overflow. We assume it is not possible for 241 // in memory strings to overflow a uint64_t. 242 uint64_t result_size = start_value.size(); 243 for (Iterator it = start; ++it != end;) { 244 result_size += s.size(); 245 result_size += (*it).size(); 246 } 247 248 if (result_size > 0) { 249 constexpr uint64_t kMaxSize = 250 uint64_t{(std::numeric_limits<size_t>::max)()}; 251 ABSL_INTERNAL_CHECK(result_size <= kMaxSize, "size_t overflow"); 252 STLStringResizeUninitialized(&result, static_cast<size_t>(result_size)); 253 254 // Joins strings 255 char* result_buf = &*result.begin(); 256 257 memcpy(result_buf, start_value.data(), start_value.size()); 258 result_buf += start_value.size(); 259 for (Iterator it = start; ++it != end;) { 260 memcpy(result_buf, s.data(), s.size()); 261 result_buf += s.size(); 262 auto&& value = *it; 263 memcpy(result_buf, value.data(), value.size()); 264 result_buf += value.size(); 265 } 266 } 267 } 268 269 return result; 270 } 271 272 // JoinTupleLoop implements a loop over the elements of a std::tuple, which 273 // are heterogeneous. The primary template matches the tuple interior case. It 274 // continues the iteration after appending a separator (for nonzero indices) 275 // and formatting an element of the tuple. The specialization for the I=N case 276 // matches the end-of-tuple, and terminates the iteration. 277 template <size_t I, size_t N> 278 struct JoinTupleLoop { 279 template <typename Tup, typename Formatter> 280 void operator()(std::string* out, const Tup& tup, absl::string_view sep, 281 Formatter&& fmt) { 282 if (I > 0) out->append(sep.data(), sep.size()); 283 fmt(out, std::get<I>(tup)); 284 JoinTupleLoop<I + 1, N>()(out, tup, sep, fmt); 285 } 286 }; 287 template <size_t N> 288 struct JoinTupleLoop<N, N> { 289 template <typename Tup, typename Formatter> 290 void operator()(std::string*, const Tup&, absl::string_view, Formatter&&) {} 291 }; 292 293 template <typename... T, typename Formatter> 294 std::string JoinAlgorithm(const std::tuple<T...>& tup, absl::string_view sep, 295 Formatter&& fmt) { 296 std::string result; 297 JoinTupleLoop<0, sizeof...(T)>()(&result, tup, sep, fmt); 298 return result; 299 } 300 301 template <typename Iterator> 302 std::string JoinRange(Iterator first, Iterator last, 303 absl::string_view separator) { 304 // No formatter was explicitly given, so a default must be chosen. 305 typedef typename std::iterator_traits<Iterator>::value_type ValueType; 306 typedef typename DefaultFormatter<ValueType>::Type Formatter; 307 return JoinAlgorithm(first, last, separator, Formatter()); 308 } 309 310 template <typename Range, typename Formatter> 311 std::string JoinRange(const Range& range, absl::string_view separator, 312 Formatter&& fmt) { 313 using std::begin; 314 using std::end; 315 return JoinAlgorithm(begin(range), end(range), separator, fmt); 316 } 317 318 template <typename Range> 319 std::string JoinRange(const Range& range, absl::string_view separator) { 320 using std::begin; 321 using std::end; 322 return JoinRange(begin(range), end(range), separator); 323 } 324 325 template <typename Tuple, std::size_t... I> 326 std::string JoinTuple(const Tuple& value, absl::string_view separator, 327 std::index_sequence<I...>) { 328 return JoinRange( 329 std::initializer_list<absl::string_view>{ 330 static_cast<const AlphaNum&>(std::get<I>(value)).Piece()...}, 331 separator); 332 } 333 334 } // namespace strings_internal 335 ABSL_NAMESPACE_END 336 } // namespace absl 337 338 #endif // ABSL_STRINGS_INTERNAL_STR_JOIN_INTERNAL_H_