X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Fjson.cpp;h=fe031120f3f46eb0931a903504f0f478a8aeabe8;hb=d7b6ad4972b288f90bf57d7597103c44c244decd;hp=4449e7799d147c04dd905728ca3d538752abad40;hpb=266c83777e21943f98cef4cb6cede367f083ba51;p=folly.git diff --git a/folly/json.cpp b/folly/json.cpp index 4449e779..fe031120 100644 --- a/folly/json.cpp +++ b/folly/json.cpp @@ -1,5 +1,5 @@ /* - * Copyright 2017 Facebook, Inc. + * Copyright 2011-present Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -13,21 +13,21 @@ * See the License for the specific language governing permissions and * limitations under the License. */ - #include #include -#include #include +#include -#include #include +#include #include #include #include #include #include +#include #include namespace folly { @@ -84,7 +84,7 @@ struct Printer { } } -private: + private: void printKV(const std::pair& p) const { if (!opts_.allow_non_string_keys && !p.first.isString()) { throw std::runtime_error("folly::toJson: JSON object key was not a " @@ -114,12 +114,17 @@ private: out_ += '{'; indent(); newline(); - if (opts_.sort_keys) { + if (opts_.sort_keys || opts_.sort_keys_by) { using ref = std::reference_wrapper; std::vector refs(o.items().begin(), o.items().end()); - std::sort(refs.begin(), refs.end(), [](ref a, ref b) { + + using SortByRef = FunctionRef; + auto const& sort_keys_by = opts_.sort_keys_by + ? SortByRef(opts_.sort_keys_by) + : SortByRef(std::less()); + std::sort(refs.begin(), refs.end(), [&](ref a, ref b) { // Only compare keys. No ordering among identical keys. - return a.get().first < b.get().first; + return sort_keys_by(a.get().first, b.get().first); }); printKVPairs(refs.cbegin(), refs.cend()); } else { @@ -150,7 +155,7 @@ private: out_ += ']'; } -private: + private: void outdent() const { if (indentLevel_) { --*indentLevel_; @@ -173,31 +178,26 @@ private: out_ += indentLevel_ ? " : " : ":"; } -private: - std::string& out_; - unsigned* const indentLevel_; - serialization_opts const& opts_; + private: + std::string& out_; + unsigned* const indentLevel_; + serialization_opts const& opts_; }; - ////////////////////////////////////////////////////////////////////// - - struct ParseError : std::runtime_error { - explicit ParseError(int line) - : std::runtime_error(to("json parse error on line ", line)) - {} - - explicit ParseError(int line, std::string const& context, - std::string const& expected) - : std::runtime_error(to("json parse error on line ", line, - !context.empty() ? to(" near `", context, '\'') - : "", - ": ", expected)) - {} +////////////////////////////////////////////////////////////////////// - explicit ParseError(std::string const& msg) - : std::runtime_error("json parse error: " + msg) - {} - }; +struct FOLLY_EXPORT ParseError : std::runtime_error { + explicit ParseError( + unsigned int line, + std::string const& context, + std::string const& expected) + : std::runtime_error(to( + "json parse error on line ", + line, + !context.empty() ? to(" near `", context, '\'') : "", + ": ", + expected)) {} +}; // Wraps our input buffer with some helper functions. struct Input { @@ -216,7 +216,7 @@ struct Input { // Parse ahead for as long as the supplied predicate is satisfied, // returning a range of what was skipped. - template + template StringPiece skipWhile(const Predicate& p) { std::size_t skipped = 0; for (; skipped < range_.size(); ++skipped) { @@ -272,7 +272,7 @@ struct Input { storeCurrent(); } - template + template T extract() { try { return to(&range_); @@ -318,7 +318,7 @@ struct Input { current_ = range_.empty() ? EOF : range_.front(); } -private: + private: StringPiece range_; json::serialization_opts const& opts_; unsigned lineNum_; @@ -345,7 +345,7 @@ std::string parseString(Input& in); dynamic parseNumber(Input& in); dynamic parseObject(Input& in) { - assert(*in == '{'); + DCHECK_EQ(*in, '{'); ++in; dynamic ret = dynamic::object; @@ -389,7 +389,7 @@ dynamic parseObject(Input& in) { } dynamic parseArray(Input& in) { - assert(*in == '['); + DCHECK_EQ(*in, '['); ++in; dynamic ret = dynamic::array; @@ -488,7 +488,7 @@ std::string decodeUnicodeEscape(Input& in) { in.error("expected 4 hex digits"); } - uint16_t ret = hexVal(*in) * 4096; + uint16_t ret = uint16_t(hexVal(*in) * 4096); ++in; ret += hexVal(*in) * 256; ++in; @@ -524,7 +524,7 @@ std::string decodeUnicodeEscape(Input& in) { } std::string parseString(Input& in) { - assert(*in == '\"'); + DCHECK_EQ(*in, '\"'); ++in; std::string ret; @@ -596,7 +596,7 @@ dynamic parseValue(Input& in) { in.error("expected json value"); } -} +} // namespace ////////////////////////////////////////////////////////////////////// @@ -608,6 +608,44 @@ std::string serialize(dynamic const& dyn, serialization_opts const& opts) { return ret; } +// Fast path to determine the longest prefix that can be left +// unescaped in a string of sizeof(T) bytes packed in an integer of +// type T. +template +size_t firstEscapableInWord(T s) { + static_assert(std::is_unsigned::value, "Unsigned integer required"); + static constexpr T kOnes = ~T() / 255; // 0x...0101 + static constexpr T kMsbs = kOnes * 0x80; // 0x...8080 + + // Sets the MSB of bytes < b. Precondition: b < 128. + auto isLess = [](T w, uint8_t b) { + // A byte is < b iff subtracting b underflows, so we check that + // the MSB wasn't set before and it's set after the subtraction. + return (w - kOnes * b) & ~w & kMsbs; + }; + + auto isChar = [&](uint8_t c) { + // A byte is == c iff it is 0 if xored with c. + return isLess(s ^ (kOnes * c), 1); + }; + + // The following masks have the MSB set for each byte of the word + // that satisfies the corresponding condition. + auto isHigh = s & kMsbs; // >= 128 + auto isLow = isLess(s, 0x20); // <= 0x1f + auto needsEscape = isHigh | isLow | isChar('\\') | isChar('"'); + + if (!needsEscape) { + return sizeof(T); + } + + if (folly::kIsLittleEndian) { + return folly::findFirstSet(needsEscape) / 8 - 1; + } else { + return sizeof(T) - folly::findLastSet(needsEscape) / 8; + } +} + // Escape a string so that it is legal to print it in JSON text. void escapeString( StringPiece input, @@ -624,18 +662,48 @@ void escapeString( auto* e = reinterpret_cast(input.end()); while (p < e) { + // Find the longest prefix that does not need escaping, and copy + // it literally into the output string. + auto firstEsc = p; + while (firstEsc < e) { + auto avail = e - firstEsc; + uint64_t word = 0; + if (avail >= 8) { + word = folly::loadUnaligned(firstEsc); + } else { + memcpy(static_cast(&word), firstEsc, avail); + } + auto prefix = firstEscapableInWord(word); + DCHECK_LE(prefix, avail); + firstEsc += prefix; + if (prefix < 8) { + break; + } + } + if (firstEsc > p) { + out.append(reinterpret_cast(p), firstEsc - p); + p = firstEsc; + // We can't be in the middle of a multibyte sequence, so we can reset q. + q = p; + if (p == e) { + break; + } + } + + // Handle the next byte that may need escaping. + // Since non-ascii encoding inherently does utf8 validation // we explicitly validate utf8 only if non-ascii encoding is disabled. if ((opts.validate_utf8 || opts.skip_invalid_utf8) && !opts.encode_non_ascii) { - // to achieve better spatial and temporal coherence + // To achieve better spatial and temporal coherence // we do utf8 validation progressively along with the - // string-escaping instead of two separate passes + // string-escaping instead of two separate passes. - // as the encoding progresses, q will stay at or ahead of p - CHECK(q >= p); + // As the encoding progresses, q will stay at or ahead of p. + CHECK_GE(q, p); - // as p catches up with q, move q forward + // As p catches up with q, move q forward. if (q == p) { // calling utf8_decode has the side effect of // checking that utf8 encodings are valid @@ -651,14 +719,16 @@ void escapeString( // note that this if condition captures utf8 chars // with value > 127, so size > 1 byte char32_t v = utf8ToCodePoint(p, e, opts.skip_invalid_utf8); - out.append("\\u"); - out.push_back(hexDigit(uint8_t(v >> 12))); - out.push_back(hexDigit((v >> 8) & 0x0f)); - out.push_back(hexDigit((v >> 4) & 0x0f)); - out.push_back(hexDigit(v & 0x0f)); + char buf[] = "\\u\0\0\0\0"; + buf[2] = hexDigit(uint8_t(v >> 12)); + buf[3] = hexDigit((v >> 8) & 0x0f); + buf[4] = hexDigit((v >> 4) & 0x0f); + buf[5] = hexDigit(v & 0x0f); + out.append(buf, 6); } else if (*p == '\\' || *p == '\"') { - out.push_back('\\'); - out.push_back(char(*p++)); + char buf[] = "\\\0"; + buf[1] = char(*p++); + out.append(buf, 2); } else if (*p <= 0x1f) { switch (*p) { case '\b': out.append("\\b"); p++; break; @@ -667,15 +737,16 @@ void escapeString( case '\r': out.append("\\r"); p++; break; case '\t': out.append("\\t"); p++; break; default: - // note that this if condition captures non readable chars + // Note that this if condition captures non readable chars // with value < 32, so size = 1 byte (e.g control chars). - out.append("\\u00"); - out.push_back(hexDigit((*p & 0xf0) >> 4)); - out.push_back(hexDigit(*p & 0xf)); + char buf[] = "\\u00\0\0"; + buf[4] = hexDigit(uint8_t((*p & 0xf0) >> 4)); + buf[5] = hexDigit(uint8_t(*p & 0xf)); + out.append(buf, 6); p++; } } else { - out.push_back(*p++); + out.push_back(char(*p++)); } } @@ -741,7 +812,7 @@ std::string stripComments(StringPiece jsonC) { return result; } -} +} // namespace json ////////////////////////////////////////////////////////////////////// @@ -796,4 +867,4 @@ void PrintTo(const dynamic& dyn, std::ostream* os) { ////////////////////////////////////////////////////////////////////// -} +} // namespace folly