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_piece.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':
           decoded_str.push_back('\b');
           break;
         case 'f':
           decoded_str.push_back('\f');
           break;
         case 'n':
           decoded_str.push_back('\n');
           break;
         case 'r':
           decoded_str.push_back('\r');
           break;
         case 't':
           decoded_str.push_back('\t');
           break;
         case 'v':
           decoded_str.push_back('\v');
           break;
 
         case 'x':
           decoded_str.push_back((HexDigitToInt(*(token.begin + i + 1)) << 4) +

[Mark Mentovai, 2012/03/22 21:06:20]

HexStringToInt here too?

                                 HexDigitToInt(*(token.begin + i + 2)));

[Mark Mentovai, 2012/03/22 21:06:20]

All of this +1, +2, +3 stuff seems kind of unsafe.

[brettw, 2012/03/23 16:29:24]

Let's do Mark's suggestion. It's minor compared to the risk of the rest of this
patch, and this code is clearly wrong (not checking the bounds or hex digit
validity). Lots of times people don't get around to the refactoring they mean to
get to, so I'd rather not put off this minor fix.

[Robert Sesek, 2012/03/23 18:40:27]

Fine, done.

If it was wrong for 18 releases, I don't see how one more would hurt though ;).

           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)));
-          i += 4;
+          if (!ConvertUTF16Units(token, &i, &decoded_str))
+            return NULL;
           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);
+}
+
+bool JSONReader::ConvertUTF16Units(const Token& token,
+                                   int* i,
+                                   std::string* dest_string) {
+  if (*i + 4 >= token.length)
+    return false;
+
+  // 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.
+  // Consume the UTF-16 code unit, which may be a high surrogate.
+  int code_unit16_high = 0;
+  if (!HexStringToInt(StringPiece(token.begin + *i + 1, 4), &code_unit16_high))
+    return false;
+  *i += 4;
+
+  // If this is a high surrogate, consume the next code unit to get the
+  // low surrogate.
+  int 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 false;
+
+    // Make sure that the token has more characters to consume the
+    // lower surrogate.
+    if (*i + 6 >= token.length)
+      return false;
+    if (*(++(*i) + token.begin) != '\\' || *(++(*i) + token.begin) != 'u')
+      return false;
+
+    if (!HexStringToInt(StringPiece(token.begin + *i + 1, 4), &code_unit16_low))
+      return false;
+    *i += 4;
+    if (!CBU16_IS_SURROGATE(code_unit16_low) ||
+        !CBU16_IS_TRAIL(code_unit16_low)) {
+      return false;
+    }
+  } else if (!CBU16_IS_SINGLE(code_unit16_high)) {
+    // If this is not a code point, it's an encoding error.
+    return false;
+  }
+
+  // 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);
+  }
+  dest_string->append(code_point);
+  return true;
 }
 
 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