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