2 * Copyright 2015 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef FOLLY_STRING_INL_H_
18 #define FOLLY_STRING_INL_H_
23 #ifndef FOLLY_BASE_STRING_H_
24 #error This file may only be included from String.h
30 // Map from character code to value of one-character escape sequence
31 // ('\n' = 10 maps to 'n'), 'O' if the character should be printed as
32 // an octal escape sequence, or 'P' if the character is printable and
33 // should be printed as is.
34 extern const char cEscapeTable[];
37 template <class String>
38 void cEscape(StringPiece str, String& out) {
41 out.reserve(out.size() + str.size());
43 auto last = p; // last regular character
44 // We advance over runs of regular characters (printable, not double-quote or
45 // backslash) and copy them in one go; this is faster than calling push_back
47 while (p != str.end()) {
49 unsigned char v = static_cast<unsigned char>(c);
50 char e = detail::cEscapeTable[v];
51 if (e == 'P') { // printable
53 } else if (e == 'O') { // octal
54 out.append(&*last, p - last);
55 esc[1] = '0' + ((v >> 6) & 7);
56 esc[2] = '0' + ((v >> 3) & 7);
57 esc[3] = '0' + (v & 7);
61 } else { // special 1-character escape
62 out.append(&*last, p - last);
69 out.append(&*last, p - last);
73 // Map from the character code of the character following a backslash to
74 // the unescaped character if a valid one-character escape sequence
75 // ('n' maps to 10 = '\n'), 'O' if this is the first character of an
76 // octal escape sequence, 'X' if this is the first character of a
77 // hexadecimal escape sequence, or 'I' if this escape sequence is invalid.
78 extern const char cUnescapeTable[];
80 // Map from the character code to the hex value, or 16 if invalid hex char.
81 extern const unsigned char hexTable[];
84 template <class String>
85 void cUnescape(StringPiece str, String& out, bool strict) {
86 out.reserve(out.size() + str.size());
88 auto last = p; // last regular character (not part of an escape sequence)
89 // We advance over runs of regular characters (not backslash) and copy them
90 // in one go; this is faster than calling push_back repeatedly.
91 while (p != str.end()) {
93 if (c != '\\') { // normal case
97 out.append(&*last, p - last);
98 if (p == str.end()) { // backslash at end of string
100 throw std::invalid_argument("incomplete escape sequence");
107 char e = detail::cUnescapeTable[static_cast<unsigned char>(*p)];
108 if (e == 'O') { // octal
109 unsigned char val = 0;
110 for (int i = 0; i < 3 && p != str.end() && *p >= '0' && *p <= '7';
112 val = (val << 3) | (*p - '0');
116 } else if (e == 'X') { // hex
118 if (p == str.end()) { // \x at end of string
120 throw std::invalid_argument("incomplete hex escape sequence");
126 unsigned char val = 0;
128 for (; (p != str.end() &&
129 (h = detail::hexTable[static_cast<unsigned char>(*p)]) < 16);
131 val = (val << 4) | h;
135 } else if (e == 'I') { // invalid
137 throw std::invalid_argument("invalid escape sequence");
143 } else { // standard escape sequence, \' etc
149 out.append(&*last, p - last);
153 // Map from character code to escape mode:
156 // 2 = pass through in PATH mode
157 // 3 = space, replace with '+' in QUERY mode
158 // 4 = percent-encode
159 extern const unsigned char uriEscapeTable[];
160 } // namespace detail
162 template <class String>
163 void uriEscape(StringPiece str, String& out, UriEscapeMode mode) {
164 static const char hexValues[] = "0123456789abcdef";
167 // Preallocate assuming that 25% of the input string will be escaped
168 out.reserve(out.size() + str.size() + 3 * (str.size() / 4));
169 auto p = str.begin();
170 auto last = p; // last regular character
171 // We advance over runs of passthrough characters and copy them in one go;
172 // this is faster than calling push_back repeatedly.
173 unsigned char minEncode = static_cast<unsigned char>(mode);
174 while (p != str.end()) {
176 unsigned char v = static_cast<unsigned char>(c);
177 unsigned char discriminator = detail::uriEscapeTable[v];
178 if (LIKELY(discriminator <= minEncode)) {
180 } else if (mode == UriEscapeMode::QUERY && discriminator == 3) {
181 out.append(&*last, p - last);
186 out.append(&*last, p - last);
187 esc[1] = hexValues[v >> 4];
188 esc[2] = hexValues[v & 0x0f];
194 out.append(&*last, p - last);
197 template <class String>
198 void uriUnescape(StringPiece str, String& out, UriEscapeMode mode) {
199 out.reserve(out.size() + str.size());
200 auto p = str.begin();
202 // We advance over runs of passthrough characters and copy them in one go;
203 // this is faster than calling push_back repeatedly.
204 while (p != str.end()) {
209 if (UNLIKELY(std::distance(p, str.end()) < 3)) {
210 throw std::invalid_argument("incomplete percent encode sequence");
212 auto h1 = detail::hexTable[static_cast<unsigned char>(p[1])];
213 auto h2 = detail::hexTable[static_cast<unsigned char>(p[2])];
214 if (UNLIKELY(h1 == 16 || h2 == 16)) {
215 throw std::invalid_argument("invalid percent encode sequence");
217 out.append(&*last, p - last);
218 out.push_back((h1 << 4) | h2);
224 if (mode == UriEscapeMode::QUERY) {
225 out.append(&*last, p - last);
237 out.append(&*last, p - last);
243 * The following functions are type-overloaded helpers for
246 inline size_t delimSize(char) { return 1; }
247 inline size_t delimSize(StringPiece s) { return s.size(); }
248 inline bool atDelim(const char* s, char c) {
251 inline bool atDelim(const char* s, StringPiece sp) {
252 return !std::memcmp(s, sp.start(), sp.size());
255 // These are used to short-circuit internalSplit() in the case of
256 // 1-character strings.
257 inline char delimFront(char c) {
258 // This one exists only for compile-time; it should never be called.
262 inline char delimFront(StringPiece s) {
263 assert(!s.empty() && s.start() != nullptr);
268 * These output conversion templates allow us to support multiple
269 * output string types, even when we are using an arbitrary
272 template<class OutStringT> struct OutputConverter {};
274 template<> struct OutputConverter<std::string> {
275 std::string operator()(StringPiece sp) const {
276 return sp.toString();
280 template<> struct OutputConverter<fbstring> {
281 fbstring operator()(StringPiece sp) const {
282 return sp.toFbstring();
286 template<> struct OutputConverter<StringPiece> {
287 StringPiece operator()(StringPiece sp) const { return sp; }
291 * Shared implementation for all the split() overloads.
293 * This uses some external helpers that are overloaded to let this
294 * algorithm be more performant if the deliminator is a single
295 * character instead of a whole string.
297 * @param ignoreEmpty iff true, don't copy empty segments to output
299 template<class OutStringT, class DelimT, class OutputIterator>
300 void internalSplit(DelimT delim, StringPiece sp, OutputIterator out,
302 assert(sp.empty() || sp.start() != nullptr);
304 const char* s = sp.start();
305 const size_t strSize = sp.size();
306 const size_t dSize = delimSize(delim);
308 OutputConverter<OutStringT> conv;
310 if (dSize > strSize || dSize == 0) {
311 if (!ignoreEmpty || strSize > 0) {
316 if (boost::is_same<DelimT,StringPiece>::value && dSize == 1) {
317 // Call the char version because it is significantly faster.
318 return internalSplit<OutStringT>(delimFront(delim), sp, out,
322 size_t tokenStartPos = 0;
323 size_t tokenSize = 0;
324 for (size_t i = 0; i <= strSize - dSize; ++i) {
325 if (atDelim(&s[i], delim)) {
326 if (!ignoreEmpty || tokenSize > 0) {
327 *out++ = conv(StringPiece(&s[tokenStartPos], tokenSize));
330 tokenStartPos = i + dSize;
337 tokenSize = strSize - tokenStartPos;
338 if (!ignoreEmpty || tokenSize > 0) {
339 *out++ = conv(StringPiece(&s[tokenStartPos], tokenSize));
343 template<class String> StringPiece prepareDelim(const String& s) {
344 return StringPiece(s);
346 inline char prepareDelim(char c) { return c; }
351 static Dst from(const Src& src) { return folly::to<Dst>(src); }
352 static Dst from(const Dst& src) { return src; }
358 typename std::enable_if<IsSplitTargetType<OutputType>::value, bool>::type
359 splitFixed(const Delim& delimiter,
362 if (exact && UNLIKELY(std::string::npos != input.find(delimiter))) {
365 out = convertTo<OutputType>::from(input);
372 class... OutputTypes>
373 typename std::enable_if<IsSplitTargetType<OutputType>::value, bool>::type
374 splitFixed(const Delim& delimiter,
377 OutputTypes&... outTail) {
378 size_t cut = input.find(delimiter);
379 if (UNLIKELY(cut == std::string::npos)) {
382 StringPiece head(input.begin(), input.begin() + cut);
383 StringPiece tail(input.begin() + cut + detail::delimSize(delimiter),
385 if (LIKELY(splitFixed<exact>(delimiter, tail, outTail...))) {
386 outHead = convertTo<OutputType>::from(head);
394 //////////////////////////////////////////////////////////////////////
396 template<class Delim, class String, class OutputType>
397 void split(const Delim& delimiter,
399 std::vector<OutputType>& out,
401 detail::internalSplit<OutputType>(
402 detail::prepareDelim(delimiter),
404 std::back_inserter(out),
408 template<class Delim, class String, class OutputType>
409 void split(const Delim& delimiter,
411 fbvector<OutputType>& out,
413 detail::internalSplit<OutputType>(
414 detail::prepareDelim(delimiter),
416 std::back_inserter(out),
420 template<class OutputValueType, class Delim, class String,
421 class OutputIterator>
422 void splitTo(const Delim& delimiter,
426 detail::internalSplit<OutputValueType>(
427 detail::prepareDelim(delimiter),
436 class... OutputTypes>
437 typename std::enable_if<IsSplitTargetType<OutputType>::value, bool>::type
438 split(const Delim& delimiter,
441 OutputTypes&... outTail) {
442 return detail::splitFixed<exact>(
443 detail::prepareDelim(delimiter),
452 * If a type can have its string size determined cheaply, we can more
453 * efficiently append it in a loop (see internalJoinAppend). Note that the
454 * struct need not conform to the std::string api completely (ex. does not need
455 * to implement append()).
457 template <class T> struct IsSizableString {
458 enum { value = IsSomeString<T>::value
459 || std::is_same<T, StringPiece>::value };
462 template <class Iterator>
463 struct IsSizableStringContainerIterator :
464 IsSizableString<typename std::iterator_traits<Iterator>::value_type> {
467 template <class Delim, class Iterator, class String>
468 void internalJoinAppend(Delim delimiter,
472 assert(begin != end);
473 if (std::is_same<Delim, StringPiece>::value &&
474 delimSize(delimiter) == 1) {
475 internalJoinAppend(delimFront(delimiter), begin, end, output);
478 toAppend(*begin, &output);
479 while (++begin != end) {
480 toAppend(delimiter, *begin, &output);
484 template <class Delim, class Iterator, class String>
485 typename std::enable_if<IsSizableStringContainerIterator<Iterator>::value>::type
486 internalJoin(Delim delimiter,
494 const size_t dsize = delimSize(delimiter);
496 size_t size = it->size();
497 while (++it != end) {
498 size += dsize + it->size();
500 output.reserve(size);
501 internalJoinAppend(delimiter, begin, end, output);
504 template <class Delim, class Iterator, class String>
506 std::enable_if<!IsSizableStringContainerIterator<Iterator>::value>::type
507 internalJoin(Delim delimiter,
515 internalJoinAppend(delimiter, begin, end, output);
518 } // namespace detail
520 template <class Delim, class Iterator, class String>
521 void join(const Delim& delimiter,
525 detail::internalJoin(
526 detail::prepareDelim(delimiter),
532 template <class String1, class String2>
533 void backslashify(const String1& input, String2& output, bool hex_style) {
534 static const char hexValues[] = "0123456789abcdef";
536 output.reserve(3 * input.size());
537 for (unsigned char c : input) {
538 // less than space or greater than '~' are considered unprintable
539 if (c < 0x20 || c > 0x7e || c == '\\') {
540 bool hex_append = false;
541 output.push_back('\\');
545 if (c == '\r') output += 'r';
546 else if (c == '\n') output += 'n';
547 else if (c == '\t') output += 't';
548 else if (c == '\a') output += 'a';
549 else if (c == '\b') output += 'b';
550 else if (c == '\0') output += '0';
551 else if (c == '\\') output += '\\';
557 output.push_back('x');
558 output.push_back(hexValues[(c >> 4) & 0xf]);
559 output.push_back(hexValues[c & 0xf]);
567 template <class String1, class String2>
568 void humanify(const String1& input, String2& output) {
569 size_t numUnprintable = 0;
570 size_t numPrintablePrefix = 0;
571 for (unsigned char c : input) {
572 if (c < 0x20 || c > 0x7e || c == '\\') {
575 if (numUnprintable == 0) {
576 ++numPrintablePrefix;
580 // hexlify doubles a string's size; backslashify can potentially
581 // explode it by 4x. Now, the printable range of the ascii
582 // "spectrum" is around 95 out of 256 values, so a "random" binary
583 // string should be around 60% unprintable. We use a 50% hueristic
584 // here, so if a string is 60% unprintable, then we just use hex
585 // output. Otherwise we backslash.
587 // UTF8 is completely ignored; as a result, utf8 characters will
588 // likely be \x escaped (since most common glyphs fit in two bytes).
589 // This is a tradeoff of complexity/speed instead of a convenience
590 // that likely would rarely matter. Moreover, this function is more
591 // about displaying underlying bytes, not about displaying glyphs
593 if (numUnprintable == 0) {
595 } else if (5 * numUnprintable >= 3 * input.size()) {
596 // However! If we have a "meaningful" prefix of printable
597 // characters, say 20% of the string, we backslashify under the
598 // assumption viewing the prefix as ascii is worth blowing the
599 // output size up a bit.
600 if (5 * numPrintablePrefix >= input.size()) {
601 backslashify(input, output);
604 hexlify(input, output, true /* append output */);
607 backslashify(input, output);
611 template<class InputString, class OutputString>
612 bool hexlify(const InputString& input, OutputString& output,
613 bool append_output) {
614 if (!append_output) output.clear();
616 static char hexValues[] = "0123456789abcdef";
617 auto j = output.size();
618 output.resize(2 * input.size() + output.size());
619 for (size_t i = 0; i < input.size(); ++i) {
621 output[j++] = hexValues[(ch >> 4) & 0xf];
622 output[j++] = hexValues[ch & 0xf];
627 template<class InputString, class OutputString>
628 bool unhexlify(const InputString& input, OutputString& output) {
629 if (input.size() % 2 != 0) {
632 output.resize(input.size() / 2);
634 auto unhex = [](char c) -> int {
635 return c >= '0' && c <= '9' ? c - '0' :
636 c >= 'A' && c <= 'F' ? c - 'A' + 10 :
637 c >= 'a' && c <= 'f' ? c - 'a' + 10 :
641 for (size_t i = 0; i < input.size(); i += 2) {
642 int highBits = unhex(input[i]);
643 int lowBits = unhex(input[i + 1]);
644 if (highBits < 0 || lowBits < 0) {
647 output[j++] = (highBits << 4) + lowBits;
654 * Hex-dump at most 16 bytes starting at offset from a memory area of size
655 * bytes. Return the number of bytes actually dumped.
657 size_t hexDumpLine(const void* ptr, size_t offset, size_t size,
659 } // namespace detail
661 template <class OutIt>
662 void hexDump(const void* ptr, size_t size, OutIt out) {
665 while (offset < size) {
666 offset += detail::hexDumpLine(ptr, offset, size, line);
673 #endif /* FOLLY_STRING_INL_H_ */