2 * Copyright 2016 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.
22 #ifndef FOLLY_STRING_H_
23 #error This file may only be included from String.h
29 // Map from character code to value of one-character escape sequence
30 // ('\n' = 10 maps to 'n'), 'O' if the character should be printed as
31 // an octal escape sequence, or 'P' if the character is printable and
32 // should be printed as is.
33 extern const char cEscapeTable[];
36 template <class String>
37 void cEscape(StringPiece str, String& out) {
40 out.reserve(out.size() + str.size());
42 auto last = p; // last regular character
43 // We advance over runs of regular characters (printable, not double-quote or
44 // backslash) and copy them in one go; this is faster than calling push_back
46 while (p != str.end()) {
48 unsigned char v = static_cast<unsigned char>(c);
49 char e = detail::cEscapeTable[v];
50 if (e == 'P') { // printable
52 } else if (e == 'O') { // octal
53 out.append(&*last, p - last);
54 esc[1] = '0' + ((v >> 6) & 7);
55 esc[2] = '0' + ((v >> 3) & 7);
56 esc[3] = '0' + (v & 7);
60 } else { // special 1-character escape
61 out.append(&*last, p - last);
68 out.append(&*last, p - last);
72 // Map from the character code of the character following a backslash to
73 // the unescaped character if a valid one-character escape sequence
74 // ('n' maps to 10 = '\n'), 'O' if this is the first character of an
75 // octal escape sequence, 'X' if this is the first character of a
76 // hexadecimal escape sequence, or 'I' if this escape sequence is invalid.
77 extern const char cUnescapeTable[];
79 // Map from the character code to the hex value, or 16 if invalid hex char.
80 extern const unsigned char hexTable[];
83 template <class String>
84 void cUnescape(StringPiece str, String& out, bool strict) {
85 out.reserve(out.size() + str.size());
87 auto last = p; // last regular character (not part of an escape sequence)
88 // We advance over runs of regular characters (not backslash) and copy them
89 // in one go; this is faster than calling push_back repeatedly.
90 while (p != str.end()) {
92 if (c != '\\') { // normal case
96 out.append(&*last, p - last);
97 if (p == str.end()) { // backslash at end of string
99 throw std::invalid_argument("incomplete escape sequence");
106 char e = detail::cUnescapeTable[static_cast<unsigned char>(*p)];
107 if (e == 'O') { // octal
108 unsigned char val = 0;
109 for (int i = 0; i < 3 && p != str.end() && *p >= '0' && *p <= '7';
111 val = (val << 3) | (*p - '0');
115 } else if (e == 'X') { // hex
117 if (p == str.end()) { // \x at end of string
119 throw std::invalid_argument("incomplete hex escape sequence");
125 unsigned char val = 0;
127 for (; (p != str.end() &&
128 (h = detail::hexTable[static_cast<unsigned char>(*p)]) < 16);
130 val = (val << 4) | h;
134 } else if (e == 'I') { // invalid
136 throw std::invalid_argument("invalid escape sequence");
142 } else { // standard escape sequence, \' etc
148 out.append(&*last, p - last);
152 // Map from character code to escape mode:
155 // 2 = pass through in PATH mode
156 // 3 = space, replace with '+' in QUERY mode
157 // 4 = percent-encode
158 extern const unsigned char uriEscapeTable[];
159 } // namespace detail
161 template <class String>
162 void uriEscape(StringPiece str, String& out, UriEscapeMode mode) {
163 static const char hexValues[] = "0123456789abcdef";
166 // Preallocate assuming that 25% of the input string will be escaped
167 out.reserve(out.size() + str.size() + 3 * (str.size() / 4));
168 auto p = str.begin();
169 auto last = p; // last regular character
170 // We advance over runs of passthrough characters and copy them in one go;
171 // this is faster than calling push_back repeatedly.
172 unsigned char minEncode = static_cast<unsigned char>(mode);
173 while (p != str.end()) {
175 unsigned char v = static_cast<unsigned char>(c);
176 unsigned char discriminator = detail::uriEscapeTable[v];
177 if (LIKELY(discriminator <= minEncode)) {
179 } else if (mode == UriEscapeMode::QUERY && discriminator == 3) {
180 out.append(&*last, p - last);
185 out.append(&*last, p - last);
186 esc[1] = hexValues[v >> 4];
187 esc[2] = hexValues[v & 0x0f];
193 out.append(&*last, p - last);
196 template <class String>
197 void uriUnescape(StringPiece str, String& out, UriEscapeMode mode) {
198 out.reserve(out.size() + str.size());
199 auto p = str.begin();
201 // We advance over runs of passthrough characters and copy them in one go;
202 // this is faster than calling push_back repeatedly.
203 while (p != str.end()) {
208 if (UNLIKELY(std::distance(p, str.end()) < 3)) {
209 throw std::invalid_argument("incomplete percent encode sequence");
211 auto h1 = detail::hexTable[static_cast<unsigned char>(p[1])];
212 auto h2 = detail::hexTable[static_cast<unsigned char>(p[2])];
213 if (UNLIKELY(h1 == 16 || h2 == 16)) {
214 throw std::invalid_argument("invalid percent encode sequence");
216 out.append(&*last, p - last);
217 out.push_back((h1 << 4) | h2);
223 if (mode == UriEscapeMode::QUERY) {
224 out.append(&*last, p - last);
236 out.append(&*last, p - last);
242 * The following functions are type-overloaded helpers for
245 inline size_t delimSize(char) { return 1; }
246 inline size_t delimSize(StringPiece s) { return s.size(); }
247 inline bool atDelim(const char* s, char c) {
250 inline bool atDelim(const char* s, StringPiece sp) {
251 return !std::memcmp(s, sp.start(), sp.size());
254 // These are used to short-circuit internalSplit() in the case of
255 // 1-character strings.
256 inline char delimFront(char c) {
257 // This one exists only for compile-time; it should never be called.
261 inline char delimFront(StringPiece s) {
262 assert(!s.empty() && s.start() != nullptr);
267 * Shared implementation for all the split() overloads.
269 * This uses some external helpers that are overloaded to let this
270 * algorithm be more performant if the deliminator is a single
271 * character instead of a whole string.
273 * @param ignoreEmpty iff true, don't copy empty segments to output
275 template<class OutStringT, class DelimT, class OutputIterator>
276 void internalSplit(DelimT delim, StringPiece sp, OutputIterator out,
278 assert(sp.empty() || sp.start() != nullptr);
280 const char* s = sp.start();
281 const size_t strSize = sp.size();
282 const size_t dSize = delimSize(delim);
284 if (dSize > strSize || dSize == 0) {
285 if (!ignoreEmpty || strSize > 0) {
286 *out++ = to<OutStringT>(sp);
290 if (boost::is_same<DelimT,StringPiece>::value && dSize == 1) {
291 // Call the char version because it is significantly faster.
292 return internalSplit<OutStringT>(delimFront(delim), sp, out,
296 size_t tokenStartPos = 0;
297 size_t tokenSize = 0;
298 for (size_t i = 0; i <= strSize - dSize; ++i) {
299 if (atDelim(&s[i], delim)) {
300 if (!ignoreEmpty || tokenSize > 0) {
301 *out++ = to<OutStringT>(sp.subpiece(tokenStartPos, tokenSize));
304 tokenStartPos = i + dSize;
311 tokenSize = strSize - tokenStartPos;
312 if (!ignoreEmpty || tokenSize > 0) {
313 *out++ = to<OutStringT>(sp.subpiece(tokenStartPos, tokenSize));
317 template<class String> StringPiece prepareDelim(const String& s) {
318 return StringPiece(s);
320 inline char prepareDelim(char c) { return c; }
322 template <bool exact, class Delim, class OutputType>
323 bool splitFixed(const Delim& delimiter, StringPiece input, OutputType& output) {
325 exact || std::is_same<OutputType, StringPiece>::value ||
326 IsSomeString<OutputType>::value,
327 "split<false>() requires that the last argument be a string type");
328 if (exact && UNLIKELY(std::string::npos != input.find(delimiter))) {
331 output = folly::to<OutputType>(input);
335 template <bool exact, class Delim, class OutputType, class... OutputTypes>
337 const Delim& delimiter,
340 OutputTypes&... outTail) {
341 size_t cut = input.find(delimiter);
342 if (UNLIKELY(cut == std::string::npos)) {
345 StringPiece head(input.begin(), input.begin() + cut);
346 StringPiece tail(input.begin() + cut + detail::delimSize(delimiter),
348 if (LIKELY(splitFixed<exact>(delimiter, tail, outTail...))) {
349 outHead = folly::to<OutputType>(head);
357 //////////////////////////////////////////////////////////////////////
359 template<class Delim, class String, class OutputType>
360 void split(const Delim& delimiter,
362 std::vector<OutputType>& out,
364 detail::internalSplit<OutputType>(
365 detail::prepareDelim(delimiter),
367 std::back_inserter(out),
371 template<class Delim, class String, class OutputType>
372 void split(const Delim& delimiter,
374 fbvector<OutputType>& out,
376 detail::internalSplit<OutputType>(
377 detail::prepareDelim(delimiter),
379 std::back_inserter(out),
383 template<class OutputValueType, class Delim, class String,
384 class OutputIterator>
385 void splitTo(const Delim& delimiter,
389 detail::internalSplit<OutputValueType>(
390 detail::prepareDelim(delimiter),
396 template <bool exact, class Delim, class... OutputTypes>
397 typename std::enable_if<
398 AllConvertible<OutputTypes...>::value && sizeof...(OutputTypes) >= 1,
400 split(const Delim& delimiter, StringPiece input, OutputTypes&... outputs) {
401 return detail::splitFixed<exact>(
402 detail::prepareDelim(delimiter), input, outputs...);
408 * If a type can have its string size determined cheaply, we can more
409 * efficiently append it in a loop (see internalJoinAppend). Note that the
410 * struct need not conform to the std::string api completely (ex. does not need
411 * to implement append()).
413 template <class T> struct IsSizableString {
414 enum { value = IsSomeString<T>::value
415 || std::is_same<T, StringPiece>::value };
418 template <class Iterator>
419 struct IsSizableStringContainerIterator :
420 IsSizableString<typename std::iterator_traits<Iterator>::value_type> {
423 template <class Delim, class Iterator, class String>
424 void internalJoinAppend(Delim delimiter,
428 assert(begin != end);
429 if (std::is_same<Delim, StringPiece>::value &&
430 delimSize(delimiter) == 1) {
431 internalJoinAppend(delimFront(delimiter), begin, end, output);
434 toAppend(*begin, &output);
435 while (++begin != end) {
436 toAppend(delimiter, *begin, &output);
440 template <class Delim, class Iterator, class String>
441 typename std::enable_if<IsSizableStringContainerIterator<Iterator>::value>::type
442 internalJoin(Delim delimiter,
450 const size_t dsize = delimSize(delimiter);
452 size_t size = it->size();
453 while (++it != end) {
454 size += dsize + it->size();
456 output.reserve(size);
457 internalJoinAppend(delimiter, begin, end, output);
460 template <class Delim, class Iterator, class String>
462 std::enable_if<!IsSizableStringContainerIterator<Iterator>::value>::type
463 internalJoin(Delim delimiter,
471 internalJoinAppend(delimiter, begin, end, output);
474 } // namespace detail
476 template <class Delim, class Iterator, class String>
477 void join(const Delim& delimiter,
481 detail::internalJoin(
482 detail::prepareDelim(delimiter),
488 template <class String1, class String2>
489 void backslashify(const String1& input, String2& output, bool hex_style) {
490 static const char hexValues[] = "0123456789abcdef";
492 output.reserve(3 * input.size());
493 for (unsigned char c : input) {
494 // less than space or greater than '~' are considered unprintable
495 if (c < 0x20 || c > 0x7e || c == '\\') {
496 bool hex_append = false;
497 output.push_back('\\');
501 if (c == '\r') output += 'r';
502 else if (c == '\n') output += 'n';
503 else if (c == '\t') output += 't';
504 else if (c == '\a') output += 'a';
505 else if (c == '\b') output += 'b';
506 else if (c == '\0') output += '0';
507 else if (c == '\\') output += '\\';
513 output.push_back('x');
514 output.push_back(hexValues[(c >> 4) & 0xf]);
515 output.push_back(hexValues[c & 0xf]);
523 template <class String1, class String2>
524 void humanify(const String1& input, String2& output) {
525 size_t numUnprintable = 0;
526 size_t numPrintablePrefix = 0;
527 for (unsigned char c : input) {
528 if (c < 0x20 || c > 0x7e || c == '\\') {
531 if (numUnprintable == 0) {
532 ++numPrintablePrefix;
536 // hexlify doubles a string's size; backslashify can potentially
537 // explode it by 4x. Now, the printable range of the ascii
538 // "spectrum" is around 95 out of 256 values, so a "random" binary
539 // string should be around 60% unprintable. We use a 50% hueristic
540 // here, so if a string is 60% unprintable, then we just use hex
541 // output. Otherwise we backslash.
543 // UTF8 is completely ignored; as a result, utf8 characters will
544 // likely be \x escaped (since most common glyphs fit in two bytes).
545 // This is a tradeoff of complexity/speed instead of a convenience
546 // that likely would rarely matter. Moreover, this function is more
547 // about displaying underlying bytes, not about displaying glyphs
549 if (numUnprintable == 0) {
551 } else if (5 * numUnprintable >= 3 * input.size()) {
552 // However! If we have a "meaningful" prefix of printable
553 // characters, say 20% of the string, we backslashify under the
554 // assumption viewing the prefix as ascii is worth blowing the
555 // output size up a bit.
556 if (5 * numPrintablePrefix >= input.size()) {
557 backslashify(input, output);
560 hexlify(input, output, true /* append output */);
563 backslashify(input, output);
567 template<class InputString, class OutputString>
568 bool hexlify(const InputString& input, OutputString& output,
569 bool append_output) {
570 if (!append_output) output.clear();
572 static char hexValues[] = "0123456789abcdef";
573 auto j = output.size();
574 output.resize(2 * input.size() + output.size());
575 for (size_t i = 0; i < input.size(); ++i) {
577 output[j++] = hexValues[(ch >> 4) & 0xf];
578 output[j++] = hexValues[ch & 0xf];
583 template<class InputString, class OutputString>
584 bool unhexlify(const InputString& input, OutputString& output) {
585 if (input.size() % 2 != 0) {
588 output.resize(input.size() / 2);
591 for (size_t i = 0; i < input.size(); i += 2) {
592 int highBits = detail::hexTable[static_cast<uint8_t>(input[i])];
593 int lowBits = detail::hexTable[static_cast<uint8_t>(input[i + 1])];
594 if ((highBits | lowBits) & 0x10) {
595 // One of the characters wasn't a hex digit
598 output[j++] = (highBits << 4) + lowBits;
605 * Hex-dump at most 16 bytes starting at offset from a memory area of size
606 * bytes. Return the number of bytes actually dumped.
608 size_t hexDumpLine(const void* ptr, size_t offset, size_t size,
610 } // namespace detail
612 template <class OutIt>
613 void hexDump(const void* ptr, size_t size, OutIt out) {
616 while (offset < size) {
617 offset += detail::hexDumpLine(ptr, offset, size, line);