X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2Fjson.cpp;h=db80b332a9b0c5825aa1a5f47f886f77993b11e6;hp=f101a7b59e20c1489a485e8641a4fd604f09f4ff;hb=c01c18b26eded07d11079a77d3df36a57fd4bf16;hpb=b197496065db412c52af324088b41efab45377d6

diff --git a/folly/json.cpp b/folly/json.cpp
index f101a7b5..db80b332 100644
--- a/folly/json.cpp
+++ b/folly/json.cpp
@@ -17,11 +17,13 @@
 #include <folly/json.h>
 
 #include <algorithm>
-#include <cassert>
 #include <functional>
+#include <type_traits>
 
-#include <boost/next_prior.hpp>
 #include <boost/algorithm/string.hpp>
+#include <boost/next_prior.hpp>
+#include <folly/Portability.h>
+#include <folly/lang/Bits.h>
 
 #include <folly/Conv.h>
 #include <folly/Range.h>
@@ -83,7 +85,7 @@ struct Printer {
     }
   }
 
-private:
+ private:
   void printKV(const std::pair<const dynamic, dynamic>& p) const {
     if (!opts_.allow_non_string_keys && !p.first.isString()) {
       throw std::runtime_error("folly::toJson: JSON object key was not a "
@@ -113,12 +115,17 @@ private:
     out_ += '{';
     indent();
     newline();
-    if (opts_.sort_keys) {
+    if (opts_.sort_keys || opts_.sort_keys_by) {
       using ref = std::reference_wrapper<decltype(o.items())::value_type const>;
       std::vector<ref> refs(o.items().begin(), o.items().end());
-      std::sort(refs.begin(), refs.end(), [](ref a, ref b) {
+
+      using SortByRef = FunctionRef<bool(dynamic const&, dynamic const&)>;
+      auto const& sort_keys_by = opts_.sort_keys_by
+          ? SortByRef(opts_.sort_keys_by)
+          : SortByRef(std::less<dynamic>());
+      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 {
@@ -149,7 +156,7 @@ private:
     out_ += ']';
   }
 
-private:
+ private:
   void outdent() const {
     if (indentLevel_) {
       --*indentLevel_;
@@ -172,31 +179,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<std::string>("json parse error on line ", line))
-    {}
-
-    explicit ParseError(int line, std::string const& context,
-        std::string const& expected)
-      : std::runtime_error(to<std::string>("json parse error on line ", line,
-          !context.empty() ? to<std::string>(" near `", context, '\'')
-                          : "",
-          ": ", expected))
-    {}
+//////////////////////////////////////////////////////////////////////
 
-    explicit ParseError(std::string const& msg)
-      : std::runtime_error("json parse error: " + msg)
-    {}
-  };
+struct ParseError : std::runtime_error {
+  explicit ParseError(
+      unsigned int line,
+      std::string const& context,
+      std::string const& expected)
+      : std::runtime_error(to<std::string>(
+            "json parse error on line ",
+            line,
+            !context.empty() ? to<std::string>(" near `", context, '\'') : "",
+            ": ",
+            expected)) {}
+};
 
 // Wraps our input buffer with some helper functions.
 struct Input {
@@ -215,7 +217,7 @@ struct Input {
 
   // Parse ahead for as long as the supplied predicate is satisfied,
   // returning a range of what was skipped.
-  template<class Predicate>
+  template <class Predicate>
   StringPiece skipWhile(const Predicate& p) {
     std::size_t skipped = 0;
     for (; skipped < range_.size(); ++skipped) {
@@ -271,7 +273,7 @@ struct Input {
     storeCurrent();
   }
 
-  template<class T>
+  template <class T>
   T extract() {
     try {
       return to<T>(&range_);
@@ -317,7 +319,7 @@ struct Input {
     current_ = range_.empty() ? EOF : range_.front();
   }
 
-private:
+ private:
   StringPiece range_;
   json::serialization_opts const& opts_;
   unsigned lineNum_;
@@ -344,7 +346,7 @@ std::string parseString(Input& in);
 dynamic parseNumber(Input& in);
 
 dynamic parseObject(Input& in) {
-  assert(*in == '{');
+  DCHECK_EQ(*in, '{');
   ++in;
 
   dynamic ret = dynamic::object;
@@ -388,7 +390,7 @@ dynamic parseObject(Input& in) {
 }
 
 dynamic parseArray(Input& in) {
-  assert(*in == '[');
+  DCHECK_EQ(*in, '[');
   ++in;
 
   dynamic ret = dynamic::array;
@@ -487,7 +489,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;
@@ -523,7 +525,7 @@ std::string decodeUnicodeEscape(Input& in) {
 }
 
 std::string parseString(Input& in) {
-  assert(*in == '\"');
+  DCHECK_EQ(*in, '\"');
   ++in;
 
   std::string ret;
@@ -595,7 +597,7 @@ dynamic parseValue(Input& in) {
          in.error("expected json value");
 }
 
-}
+} // namespace
 
 //////////////////////////////////////////////////////////////////////
 
@@ -607,6 +609,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 <class T>
+size_t firstEscapableInWord(T s) {
+  static_assert(std::is_unsigned<T>::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,
@@ -623,18 +663,48 @@ void escapeString(
   auto* e = reinterpret_cast<const unsigned char*>(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<uint64_t>(firstEsc);
+      } else {
+        memcpy(static_cast<void*>(&word), firstEsc, avail);
+      }
+      auto prefix = firstEscapableInWord(word);
+      DCHECK_LE(prefix, avail);
+      firstEsc += prefix;
+      if (prefix < 8) {
+        break;
+      }
+    }
+    if (firstEsc > p) {
+      out.append(reinterpret_cast<const char*>(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
@@ -650,14 +720,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;
@@ -666,15 +738,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++));
     }
   }
 
@@ -740,7 +813,7 @@ std::string stripComments(StringPiece jsonC) {
   return result;
 }
 
-}
+} // namespace json
 
 //////////////////////////////////////////////////////////////////////
 
@@ -795,4 +868,4 @@ void PrintTo(const dynamic& dyn, std::ostream* os) {
 
 //////////////////////////////////////////////////////////////////////
 
-}
+} // namespace folly