Improve JSONReader performance by up to 55% by using std::string instead of wstring.

base/json/json_reader.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/json/json_reader.h"
 
 #include "base/float_util.h"
 #include "base/logging.h"
 #include "base/memory/scoped_ptr.h"
 #include "base/stringprintf.h"
 #include "base/string_number_conversions.h"
 #include "base/string_util.h"
+#include "base/third_party/icu/icu_utf.h"
 #include "base/utf_string_conversions.h"
 #include "base/values.h"
 
 namespace {
 
-const wchar_t kNullString[] = L"null";
-const wchar_t kTrueString[] = L"true";
-const wchar_t kFalseString[] = L"false";
+const char kNullString[] = "null";
+const char kTrueString[] = "true";
+const char kFalseString[] = "false";
 
 const int kStackLimit = 100;
 
 // A helper method for ParseNumberToken.  It reads an int from the end of
 // token.  The method returns false if there is no valid integer at the end of
 // the token.
 bool ReadInt(base::JSONReader::Token& token, bool can_have_leading_zeros) {
-  wchar_t first = token.NextChar();
+  char first = token.NextChar();
   int len = 0;
 
   // Read in more digits.
-  wchar_t c = first;
+  char c = first;
   while ('\0' != c && IsAsciiDigit(c)) {
     ++token.length;
     ++len;
     c = token.NextChar();
   }
   // We need at least 1 digit.
   if (len == 0)
     return false;
 
   if (!can_have_leading_zeros && len > 1 && '0' == first)
     return false;
 
   return true;
 }
 
 // A helper method for ParseStringToken.  It reads |digits| hex digits from the
 // token. If the sequence if digits is not valid (contains other characters),
 // the method returns false.
 bool ReadHexDigits(base::JSONReader::Token& token, int digits) {
   for (int i = 1; i <= digits; ++i) {
-    wchar_t c = *(token.begin + token.length + i);
+    char c = *(token.begin + token.length + i);
     if (c == '\0' || !IsHexDigit(c))
       return false;
   }
 
   token.length += digits;
   return true;
 }
 
 }  // namespace
 
@@ skipping 12 matching lines @@
 const char* JSONReader::kUnexpectedDataAfterRoot =
     "Unexpected data after root element.";
 const char* JSONReader::kUnsupportedEncoding =
     "Unsupported encoding. JSON must be UTF-8.";
 const char* JSONReader::kUnquotedDictionaryKey =
     "Dictionary keys must be quoted.";
 
 JSONReader::JSONReader()
     : start_pos_(NULL),
       json_pos_(NULL),
+      end_pos_(NULL),
       stack_depth_(0),
       allow_trailing_comma_(false),
       error_code_(JSON_NO_ERROR),
       error_line_(0),
       error_col_(0) {}
 
 // static
 Value* JSONReader::Read(const std::string& json,
                         bool allow_trailing_comma) {
   return ReadAndReturnError(json, allow_trailing_comma, NULL, NULL);
@@ skipping 45 matching lines @@
 }
 
 std::string JSONReader::GetErrorMessage() const {
   return FormatErrorMessage(error_line_, error_col_,
                             ErrorCodeToString(error_code_));
 }
 
 Value* JSONReader::JsonToValue(const std::string& json, bool check_root,
                                bool allow_trailing_comma) {
   // The input must be in UTF-8.
-  if (!IsStringUTF8(json.c_str())) {
+  if (!IsStringUTF8(json.data())) {
     error_code_ = JSON_UNSUPPORTED_ENCODING;
     return NULL;
   }
 
-  // The conversion from UTF8 to wstring removes null bytes for us
-  // (a good thing).
-  std::wstring json_wide(UTF8ToWide(json));
-  start_pos_ = json_wide.c_str();
+  start_pos_ = json.data();
+  end_pos_ = start_pos_ + json.size();
 
-  // When the input JSON string starts with a UTF-8 Byte-Order-Mark
-  // (0xEF, 0xBB, 0xBF), the UTF8ToWide() function converts it to a Unicode
-  // BOM (U+FEFF). To avoid the JSONReader::BuildValue() function from
-  // mis-treating a Unicode BOM as an invalid character and returning NULL,
-  // skip a converted Unicode BOM if it exists.
-  if (!json_wide.empty() && start_pos_[0] == 0xFEFF) {
-    ++start_pos_;
+  // When the input JSON string starts with a UTF-8 Byte-Order-Mark (U+FEFF)
+  // or <0xEF 0xBB 0xBF>, advance the start position to avoid the
+  // JSONReader::BuildValue() function from mis-treating a Unicode BOM as an
+  // invalid character and returning NULL.
+  if (json.size() >= 3 && start_pos_[0] == 0xEF &&
+      start_pos_[1] == 0xBB && start_pos_[2] == 0xBF) {
+    start_pos_ += 3;
   }
 
   json_pos_ = start_pos_;
   allow_trailing_comma_ = allow_trailing_comma;
   stack_depth_ = 0;
   error_code_ = JSON_NO_ERROR;
 
   scoped_ptr<Value> root(BuildValue(check_root));
   if (root.get()) {
     if (ParseToken().type == Token::END_OF_INPUT) {
@@ skipping 171 matching lines @@
   json_pos_ += token.length;
 
   --stack_depth_;
   return node.release();
 }
 
 JSONReader::Token JSONReader::ParseNumberToken() {
   // We just grab the number here.  We validate the size in DecodeNumber.
   // According   to RFC4627, a valid number is: [minus] int [frac] [exp]
   Token token(Token::NUMBER, json_pos_, 0);
-  wchar_t c = *json_pos_;
+  char c = *json_pos_;
   if ('-' == c) {
     ++token.length;
     c = token.NextChar();
   }
 
   if (!ReadInt(token, false))
     return Token::CreateInvalidToken();
 
   // Optional fraction part
   c = token.NextChar();
@@ skipping 13 matching lines @@
       c = token.NextChar();
     }
     if (!ReadInt(token, true))
       return Token::CreateInvalidToken();
   }
 
   return token;
 }
 
 Value* JSONReader::DecodeNumber(const Token& token) {
-  const std::wstring num_string(token.begin, token.length);
+  const std::string num_string(token.begin, token.length);
 
   int num_int;
-  if (StringToInt(WideToUTF8(num_string), &num_int))
+  if (StringToInt(num_string, &num_int))
     return Value::CreateIntegerValue(num_int);
 
   double num_double;
-  if (StringToDouble(WideToUTF8(num_string), &num_double) &&
-      base::IsFinite(num_double))
+  if (StringToDouble(num_string, &num_double) && base::IsFinite(num_double))
     return Value::CreateDoubleValue(num_double);
 
   return NULL;
 }
 
 JSONReader::Token JSONReader::ParseStringToken() {
   Token token(Token::STRING, json_pos_, 1);
-  wchar_t c = token.NextChar();
-  while ('\0' != c) {
+  char c = token.NextChar();
+  while (json_pos_ + token.length < end_pos_) {
     if ('\\' == c) {
       ++token.length;
       c = token.NextChar();
       // Make sure the escaped char is valid.
       switch (c) {
         case 'x':
           if (!ReadHexDigits(token, 2)) {
             SetErrorCode(JSON_INVALID_ESCAPE, json_pos_ + token.length);
             return Token::CreateInvalidToken();
           }
@@ skipping 22 matching lines @@
       ++token.length;
       return token;
     }
     ++token.length;
     c = token.NextChar();
   }
   return Token::CreateInvalidToken();
 }
 
 Value* JSONReader::DecodeString(const Token& token) {
-  std::wstring decoded_str;
+  std::string decoded_str;
   decoded_str.reserve(token.length - 2);
 
   for (int i = 1; i < token.length - 1; ++i) {
-    wchar_t c = *(token.begin + i);
+    char c = *(token.begin + i);
     if ('\\' == c) {
       ++i;
       c = *(token.begin + i);
       switch (c) {
         case '"':
         case '/':
         case '\\':
           decoded_str.push_back(c);
           break;
         case 'b':
@@ skipping 13 matching lines @@
           break;
         case 'v':
           decoded_str.push_back('\v');
           break;
 
         case 'x':
           decoded_str.push_back((HexDigitToInt(*(token.begin + i + 1)) << 4) +
                                 HexDigitToInt(*(token.begin + i + 2)));
           i += 2;
           break;
-        case 'u':
-          decoded_str.push_back((HexDigitToInt(*(token.begin + i + 1)) << 12 ) +
-                                (HexDigitToInt(*(token.begin + i + 2)) << 8) +
-                                (HexDigitToInt(*(token.begin + i + 3)) << 4) +
-                                HexDigitToInt(*(token.begin + i + 4)));
+        case 'u': {
+          // Consume the UTF-16 code unit, which may be a high surrogate.

[brettw, 2012/03/22 05:51:42]

This case is getting kind of crazy long, can you separate this one into a
ReadUnicodeChar (or something) function?

[Robert Sesek, 2012/03/22 17:59:57]

Done.

+          if (i + 4 >= token.length)
+            return NULL;
+          uint32 code_unit16_high =
+              (HexDigitToInt(*(token.begin + i + 1)) << 12) +
+              (HexDigitToInt(*(token.begin + i + 2)) << 8) +
+              (HexDigitToInt(*(token.begin + i + 3)) << 4) +
+              HexDigitToInt(*(token.begin + i + 4));
           i += 4;
+
+          // If this is a high surrogate, consume the next code unit to get the
+          // low surrogate.
+          // This is a 32-bit field because the shift operations in the
+          // conversion process below cause MSVC to error about "data loss."
+          // This only stores UTF-16 code units, though.
+          uint32 code_unit16_low = 0;
+          if (CBU16_IS_SURROGATE(code_unit16_high)) {
+            // Make sure this is the high surrogate. If not, it's an encoding
+            // error.
+            if (!CBU16_IS_SURROGATE_LEAD(code_unit16_high))
+              return NULL;

[brettw, 2012/03/22 05:51:42]

You changed the behavior of this function by failing for different encoding
issues. Before it looks like it wouldn't fail. Are we sure we want to change
this? (It's fine if we do, I just want to make sure we understand everything.)

It also seems weird to me that this code fails for things like surrogate
problems, but not for things like \u$%@! (which will be 0).

[Robert Sesek, 2012/03/22 17:59:57]

I think we do. The JSON spec states what's legal in a string, and I think
invalid escape sequences constitute invalid JSON. I think failure is the right
approach here.
This will fail for that invalid code unit (added it to the unittest). Line 530
will validate that.

+
+            // Make sure that the token has more characters to consume the
+            // lower surrogate.
+            if (i + 6 >= token.length)
+              return NULL;
+            if (*(++i + token.begin) != '\\' || *(++i + token.begin) != 'u')
+              return NULL;
+
+            code_unit16_low =
+                (HexDigitToInt(*(token.begin + i + 1)) << 12) +

[brettw, 2012/03/22 05:51:42]

It's sort of annoying that this is duplicated twice. I wonder if another helper
function (and if we decide to be strict, it would check for errors) is in order.

[Robert Sesek, 2012/03/22 17:59:57]

Done. Can you explain what you mean by "be strict"? The first parse phase
validates that these digits are HEX.

+                (HexDigitToInt(*(token.begin + i + 2)) << 8) +
+                (HexDigitToInt(*(token.begin + i + 3)) << 4) +
+                HexDigitToInt(*(token.begin + i + 4));
+            if (!CBU16_IS_SURROGATE(code_unit16_low) ||
+                !CBU16_IS_TRAIL(code_unit16_low)) {
+              return NULL;
+            }
+            i += 4;
+          } else if (!CBU16_IS_SINGLE(code_unit16_high)) {
+            // If this is not a code point, it's an encoding error.
+            return NULL;
+          }
+
+          // Convert the UTF-16 code units to a code point and then to a UTF-8
+          // code unit sequence.
+          char code_point[8] = { 0 };
+          size_t offset = 0;
+          if (!code_unit16_low) {
+            CBU8_APPEND_UNSAFE(code_point, offset, code_unit16_high);
+          } else {
+            uint32 code_unit32 = CBU16_GET_SUPPLEMENTARY(code_unit16_high,
+                                                         code_unit16_low);
+            offset = 0;
+            CBU8_APPEND_UNSAFE(code_point, offset, code_unit32);
+          }
+          decoded_str.append(code_point);
           break;
+        }
 
         default:
           // We should only have valid strings at this point.  If not,
           // ParseStringToken didn't do it's job.
           NOTREACHED();
           return NULL;
       }
     } else {
       // Not escaped
       decoded_str.push_back(c);
     }
   }
-  return Value::CreateStringValue(WideToUTF16Hack(decoded_str));
+  return Value::CreateStringValue(decoded_str);
 }
 
 JSONReader::Token JSONReader::ParseToken() {
   EatWhitespaceAndComments();
 
   Token token(Token::INVALID_TOKEN, 0, 0);
   switch (*json_pos_) {
     case '\0':
       token.type = Token::END_OF_INPUT;
       break;
@@ skipping 52 matching lines @@
       break;
 
     case '"':
       token = ParseStringToken();
       break;
   }
   return token;
 }
 
 void JSONReader::EatWhitespaceAndComments() {
-  while ('\0' != *json_pos_) {
+  while (json_pos_ != end_pos_) {
     switch (*json_pos_) {
       case ' ':
       case '\n':
       case '\r':
       case '\t':
         ++json_pos_;
         break;
       case '/':
         // TODO(tc): This isn't in the RFC so it should be a parser flag.
         if (!EatComment())
           return;
         break;
       default:
         // Not a whitespace char, just exit.
         return;
     }
   }
 }
 
 bool JSONReader::EatComment() {
   if ('/' != *json_pos_)
     return false;
 
-  wchar_t next_char = *(json_pos_ + 1);
+  char next_char = *(json_pos_ + 1);
   if ('/' == next_char) {
     // Line comment, read until \n or \r
     json_pos_ += 2;
-    while ('\0' != *json_pos_) {
+    while (json_pos_ != end_pos_) {
       switch (*json_pos_) {
         case '\n':
         case '\r':
           ++json_pos_;
           return true;
         default:
           ++json_pos_;
       }
     }
   } else if ('*' == next_char) {
     // Block comment, read until */
     json_pos_ += 2;
-    while ('\0' != *json_pos_) {
+    while (json_pos_ != end_pos_) {
       if ('*' == *json_pos_ && '/' == *(json_pos_ + 1)) {
         json_pos_ += 2;
         return true;
       }
       ++json_pos_;
     }
   } else {
     return false;
   }
   return true;
 }
 
-bool JSONReader::NextStringMatch(const wchar_t* str, size_t length) {
-  return wcsncmp(json_pos_, str, length) == 0;
+bool JSONReader::NextStringMatch(const char* str, size_t length) {
+  return strncmp(json_pos_, str, length) == 0;
 }
 
 void JSONReader::SetErrorCode(JsonParseError error,
-                              const wchar_t* error_pos) {
+                              const char* error_pos) {
   int line_number = 1;
   int column_number = 1;
 
   // Figure out the line and column the error occured at.
-  for (const wchar_t* pos = start_pos_; pos != error_pos; ++pos) {
-    if (*pos == '\0') {
+  for (const char* pos = start_pos_; pos != error_pos; ++pos) {
+    if (pos > end_pos_) {
       NOTREACHED();
       return;
     }
 
     if (*pos == '\n') {
       ++line_number;
       column_number = 1;
     } else {
       ++column_number;
     }
   }
 
   error_line_ = line_number;
   error_col_ = column_number;
   error_code_ = error;
 }
 
 }  // namespace base