base/values.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "base/values.h"
   6
   7 #include <string.h>
   8
   9 #include <algorithm>
  10 #include <cmath>
  11 #include <new>
  12 #include <ostream>
  13 #include <utility>
  14
  15 #include "base/json/json_writer.h"
  16 #include "base/logging.h"
  17 #include "base/memory/ptr_util.h"
  18 #include "base/stl_util.h"
  19 #include "base/strings/string_util.h"
  20 #include "base/strings/utf_string_conversions.h"
  21 #include "base/trace_event/memory_usage_estimator.h"
  22
  23 namespace base {
  24
  25 namespace {
  26
  27 const char* const kTypeNames[] = {"null",   "boolean", "integer",    "double",
  28                                   "string", "binary",  "dictionary", "list"};
  29 static_assert(arraysize(kTypeNames) ==
  30                   static_cast<size_t>(Value::Type::LIST) + 1,
  31               "kTypeNames Has Wrong Size");
  32
  33 std::unique_ptr<Value> CopyWithoutEmptyChildren(const Value& node);
  34
  35 // Make a deep copy of |node|, but don't include empty lists or dictionaries
  36 // in the copy. It's possible for this function to return NULL and it
  37 // expects |node| to always be non-NULL.
  38 std::unique_ptr<Value> CopyListWithoutEmptyChildren(const Value& list) {
  39   Value copy(Value::Type::LIST);
  40   for (const auto& entry : list.GetList()) {
  41     std::unique_ptr<Value> child_copy = CopyWithoutEmptyChildren(entry);
  42     if (child_copy)
  43       copy.GetList().push_back(std::move(*child_copy));
  44   }
  45   return copy.GetList().empty() ? nullptr
  46                                 : std::make_unique<Value>(std::move(copy));
  47 }
  48
  49 std::unique_ptr<DictionaryValue> CopyDictionaryWithoutEmptyChildren(
  50     const DictionaryValue& dict) {
  51   std::unique_ptr<DictionaryValue> copy;
  52   for (DictionaryValue::Iterator it(dict); !it.IsAtEnd(); it.Advance()) {
  53     std::unique_ptr<Value> child_copy = CopyWithoutEmptyChildren(it.value());
  54     if (child_copy) {
  55       if (!copy)
  56         copy = std::make_unique<DictionaryValue>();
  57       copy->SetWithoutPathExpansion(it.key(), std::move(child_copy));
  58     }
  59   }
  60   return copy;
  61 }
  62
  63 std::unique_ptr<Value> CopyWithoutEmptyChildren(const Value& node) {
  64   switch (node.type()) {
  65     case Value::Type::LIST:
  66       return CopyListWithoutEmptyChildren(static_cast<const ListValue&>(node));
  67
  68     case Value::Type::DICTIONARY:
  69       return CopyDictionaryWithoutEmptyChildren(
  70           static_cast<const DictionaryValue&>(node));
  71
  72     default:
  73       return std::make_unique<Value>(node.Clone());
  74   }
  75 }
  76
  77 }  // namespace
  78
  79 // static
  80 std::unique_ptr<Value> Value::CreateWithCopiedBuffer(const char* buffer,
  81                                                      size_t size) {
  82   return std::make_unique<Value>(BlobStorage(buffer, buffer + size));
  83 }
  84
  85 // static
  86 Value Value::FromUniquePtrValue(std::unique_ptr<Value> val) {
  87   return std::move(*val);
  88 }
  89
  90 // static
  91 std::unique_ptr<Value> Value::ToUniquePtrValue(Value val) {
  92   return std::make_unique<Value>(std::move(val));
  93 }
  94
  95 Value::Value(Value&& that) noexcept {
  96   InternalMoveConstructFrom(std::move(that));
  97 }
  98
  99 Value::Value() noexcept : type_(Type::NONE) {}
 100
 101 Value::Value(Type type) : type_(type) {
 102   // Initialize with the default value.
 103   switch (type_) {
 104     case Type::NONE:
 105       return;
 106
 107     case Type::BOOLEAN:
 108       bool_value_ = false;
 109       return;
 110     case Type::INTEGER:
 111       int_value_ = 0;
 112       return;
 113     case Type::DOUBLE:
 114       double_value_ = 0.0;
 115       return;
 116     case Type::STRING:
 117       new (&string_value_) std::string();
 118       return;
 119     case Type::BINARY:
 120       new (&binary_value_) BlobStorage();
 121       return;
 122     case Type::DICTIONARY:
 123       new (&dict_) DictStorage();
 124       return;
 125     case Type::LIST:
 126       new (&list_) ListStorage();
 127       return;
 128   }
 129 }
 130
 131 Value::Value(bool in_bool) : type_(Type::BOOLEAN), bool_value_(in_bool) {}
 132
 133 Value::Value(int in_int) : type_(Type::INTEGER), int_value_(in_int) {}
 134
 135 Value::Value(double in_double) : type_(Type::DOUBLE), double_value_(in_double) {
 136   if (!std::isfinite(double_value_)) {
 137     NOTREACHED() << "Non-finite (i.e. NaN or positive/negative infinity) "
 138                  << "values cannot be represented in JSON";
 139     double_value_ = 0.0;
 140   }
 141 }
 142
 143 Value::Value(const char* in_string) : Value(std::string(in_string)) {}
 144
 145 Value::Value(StringPiece in_string) : Value(std::string(in_string)) {}
 146
 147 Value::Value(std::string&& in_string) noexcept
 148     : type_(Type::STRING), string_value_(std::move(in_string)) {
 149   DCHECK(IsStringUTF8(string_value_));
 150 }
 151
 152 Value::Value(const char16* in_string16) : Value(StringPiece16(in_string16)) {}
 153
 154 Value::Value(StringPiece16 in_string16) : Value(UTF16ToUTF8(in_string16)) {}
 155
 156 Value::Value(const BlobStorage& in_blob)
 157     : type_(Type::BINARY), binary_value_(in_blob) {}
 158
 159 Value::Value(BlobStorage&& in_blob) noexcept
 160     : type_(Type::BINARY), binary_value_(std::move(in_blob)) {}
 161
 162 Value::Value(const DictStorage& in_dict) : type_(Type::DICTIONARY), dict_() {
 163   dict_.reserve(in_dict.size());
 164   for (const auto& it : in_dict) {
 165     dict_.try_emplace(dict_.end(), it.first,
 166                       std::make_unique<Value>(it.second->Clone()));
 167   }
 168 }
 169
 170 Value::Value(DictStorage&& in_dict) noexcept
 171     : type_(Type::DICTIONARY), dict_(std::move(in_dict)) {}
 172
 173 Value::Value(const ListStorage& in_list) : type_(Type::LIST), list_() {
 174   list_.reserve(in_list.size());
 175   for (const auto& val : in_list)
 176     list_.emplace_back(val.Clone());
 177 }
 178
 179 Value::Value(ListStorage&& in_list) noexcept
 180     : type_(Type::LIST), list_(std::move(in_list)) {}
 181
 182 Value& Value::operator=(Value&& that) noexcept {
 183   InternalCleanup();
 184   InternalMoveConstructFrom(std::move(that));
 185
 186   return *this;
 187 }
 188
 189 Value Value::Clone() const {
 190   switch (type_) {
 191     case Type::NONE:
 192       return Value();
 193     case Type::BOOLEAN:
 194       return Value(bool_value_);
 195     case Type::INTEGER:
 196       return Value(int_value_);
 197     case Type::DOUBLE:
 198       return Value(double_value_);
 199     case Type::STRING:
 200       return Value(string_value_);
 201     case Type::BINARY:
 202       return Value(binary_value_);
 203     case Type::DICTIONARY:
 204       return Value(dict_);
 205     case Type::LIST:
 206       return Value(list_);
 207   }
 208
 209   NOTREACHED();
 210   return Value();
 211 }
 212
 213 Value::~Value() {
 214   InternalCleanup();
 215 }
 216
 217 // static
 218 const char* Value::GetTypeName(Value::Type type) {
 219   DCHECK_GE(static_cast<int>(type), 0);
 220   DCHECK_LT(static_cast<size_t>(type), arraysize(kTypeNames));
 221   return kTypeNames[static_cast<size_t>(type)];
 222 }
 223
 224 bool Value::GetBool() const {
 225   CHECK(is_bool());
 226   return bool_value_;
 227 }
 228
 229 int Value::GetInt() const {
 230   CHECK(is_int());
 231   return int_value_;
 232 }
 233
 234 double Value::GetDouble() const {
 235   if (is_double())
 236     return double_value_;
 237   if (is_int())
 238     return int_value_;
 239   CHECK(false);
 240   return 0.0;
 241 }
 242
 243 const std::string& Value::GetString() const {
 244   CHECK(is_string());
 245   return string_value_;
 246 }
 247
 248 const Value::BlobStorage& Value::GetBlob() const {
 249   CHECK(is_blob());
 250   return binary_value_;
 251 }
 252
 253 Value::ListStorage& Value::GetList() {
 254   CHECK(is_list());
 255   return list_;
 256 }
 257
 258 const Value::ListStorage& Value::GetList() const {
 259   CHECK(is_list());
 260   return list_;
 261 }
 262
 263 Value* Value::FindKey(StringPiece key) {
 264   return const_cast<Value*>(static_cast<const Value*>(this)->FindKey(key));
 265 }
 266
 267 const Value* Value::FindKey(StringPiece key) const {
 268   CHECK(is_dict());
 269   auto found = dict_.find(key);
 270   if (found == dict_.end())
 271     return nullptr;
 272   return found->second.get();
 273 }
 274
 275 Value* Value::FindKeyOfType(StringPiece key, Type type) {
 276   return const_cast<Value*>(
 277       static_cast<const Value*>(this)->FindKeyOfType(key, type));
 278 }
 279
 280 const Value* Value::FindKeyOfType(StringPiece key, Type type) const {
 281   const Value* result = FindKey(key);
 282   if (!result || result->type() != type)
 283     return nullptr;
 284   return result;
 285 }
 286
 287 bool Value::RemoveKey(StringPiece key) {
 288   CHECK(is_dict());
 289   // NOTE: Can't directly return dict_->erase(key) due to MSVC warning C4800.
 290   return dict_.erase(key) != 0;
 291 }
 292
 293 Value* Value::SetKey(StringPiece key, Value value) {
 294   CHECK(is_dict());
 295   // NOTE: We can't use |insert_or_assign| here, as only |try_emplace| does
 296   // an explicit conversion from StringPiece to std::string if necessary.
 297   auto val_ptr = std::make_unique<Value>(std::move(value));
 298   auto result = dict_.try_emplace(key, std::move(val_ptr));
 299   if (!result.second) {
 300     // val_ptr is guaranteed to be still intact at this point.
 301     result.first->second = std::move(val_ptr);
 302   }
 303   return result.first->second.get();
 304 }
 305
 306 Value* Value::SetKey(std::string&& key, Value value) {
 307   CHECK(is_dict());
 308   return dict_
 309       .insert_or_assign(std::move(key),
 310                         std::make_unique<Value>(std::move(value)))
 311       .first->second.get();
 312 }
 313
 314 Value* Value::SetKey(const char* key, Value value) {
 315   return SetKey(StringPiece(key), std::move(value));
 316 }
 317
 318 Value* Value::FindPath(std::initializer_list<StringPiece> path) {
 319   return const_cast<Value*>(const_cast<const Value*>(this)->FindPath(path));
 320 }
 321
 322 Value* Value::FindPath(span<const StringPiece> path) {
 323   return const_cast<Value*>(const_cast<const Value*>(this)->FindPath(path));
 324 }
 325
 326 const Value* Value::FindPath(std::initializer_list<StringPiece> path) const {
 327   DCHECK_GE(path.size(), 2u) << "Use FindKey() for a path of length 1.";
 328   return FindPath(make_span(path.begin(), path.size()));
 329 }
 330
 331 const Value* Value::FindPath(span<const StringPiece> path) const {
 332   const Value* cur = this;
 333   for (const StringPiece component : path) {
 334     if (!cur->is_dict() || (cur = cur->FindKey(component)) == nullptr)
 335       return nullptr;
 336   }
 337   return cur;
 338 }
 339
 340 Value* Value::FindPathOfType(std::initializer_list<StringPiece> path,
 341                              Type type) {
 342   return const_cast<Value*>(
 343       const_cast<const Value*>(this)->FindPathOfType(path, type));
 344 }
 345
 346 Value* Value::FindPathOfType(span<const StringPiece> path, Type type) {
 347   return const_cast<Value*>(
 348       const_cast<const Value*>(this)->FindPathOfType(path, type));
 349 }
 350
 351 const Value* Value::FindPathOfType(std::initializer_list<StringPiece> path,
 352                                    Type type) const {
 353   DCHECK_GE(path.size(), 2u) << "Use FindKeyOfType() for a path of length 1.";
 354   return FindPathOfType(make_span(path.begin(), path.size()), type);
 355 }
 356
 357 const Value* Value::FindPathOfType(span<const StringPiece> path,
 358                                    Type type) const {
 359   const Value* result = FindPath(path);
 360   if (!result || result->type() != type)
 361     return nullptr;
 362   return result;
 363 }
 364
 365 Value* Value::SetPath(std::initializer_list<StringPiece> path, Value value) {
 366   DCHECK_GE(path.size(), 2u) << "Use SetKey() for a path of length 1.";
 367   return SetPath(make_span(path.begin(), path.size()), std::move(value));
 368 }
 369
 370 Value* Value::SetPath(span<const StringPiece> path, Value value) {
 371   DCHECK_NE(path.begin(), path.end());  // Can't be empty path.
 372
 373   // Walk/construct intermediate dictionaries. The last element requires
 374   // special handling so skip it in this loop.
 375   Value* cur = this;
 376   const StringPiece* cur_path = path.begin();
 377   for (; (cur_path + 1) < path.end(); ++cur_path) {
 378     if (!cur->is_dict())
 379       return nullptr;
 380
 381     // Use lower_bound to avoid doing the search twice for missing keys.
 382     const StringPiece path_component = *cur_path;
 383     auto found = cur->dict_.lower_bound(path_component);
 384     if (found == cur->dict_.end() || found->first != path_component) {
 385       // No key found, insert one.
 386       auto inserted = cur->dict_.try_emplace(
 387           found, path_component, std::make_unique<Value>(Type::DICTIONARY));
 388       cur = inserted->second.get();
 389     } else {
 390       cur = found->second.get();
 391     }
 392   }
 393
 394   // "cur" will now contain the last dictionary to insert or replace into.
 395   if (!cur->is_dict())
 396     return nullptr;
 397   return cur->SetKey(*cur_path, std::move(value));
 398 }
 399
 400 bool Value::RemovePath(std::initializer_list<StringPiece> path) {
 401   DCHECK_GE(path.size(), 2u) << "Use RemoveKey() for a path of length 1.";
 402   return RemovePath(make_span(path.begin(), path.size()));
 403 }
 404
 405 bool Value::RemovePath(span<const StringPiece> path) {
 406   if (!is_dict() || path.empty())
 407     return false;
 408
 409   if (path.size() == 1)
 410     return RemoveKey(path[0]);
 411
 412   auto found = dict_.find(path[0]);
 413   if (found == dict_.end() || !found->second->is_dict())
 414     return false;
 415
 416   bool removed = found->second->RemovePath(path.subspan(1));
 417   if (removed && found->second->dict_.empty())
 418     dict_.erase(found);
 419
 420   return removed;
 421 }
 422
 423 Value::dict_iterator_proxy Value::DictItems() {
 424   CHECK(is_dict());
 425   return dict_iterator_proxy(&dict_);
 426 }
 427
 428 Value::const_dict_iterator_proxy Value::DictItems() const {
 429   CHECK(is_dict());
 430   return const_dict_iterator_proxy(&dict_);
 431 }
 432
 433 size_t Value::DictSize() const {
 434   CHECK(is_dict());
 435   return dict_.size();
 436 }
 437
 438 bool Value::DictEmpty() const {
 439   CHECK(is_dict());
 440   return dict_.empty();
 441 }
 442
 443 bool Value::GetAsBoolean(bool* out_value) const {
 444   if (out_value && is_bool()) {
 445     *out_value = bool_value_;
 446     return true;
 447   }
 448   return is_bool();
 449 }
 450
 451 bool Value::GetAsInteger(int* out_value) const {
 452   if (out_value && is_int()) {
 453     *out_value = int_value_;
 454     return true;
 455   }
 456   return is_int();
 457 }
 458
 459 bool Value::GetAsDouble(double* out_value) const {
 460   if (out_value && is_double()) {
 461     *out_value = double_value_;
 462     return true;
 463   } else if (out_value && is_int()) {
 464     // Allow promotion from int to double.
 465     *out_value = int_value_;
 466     return true;
 467   }
 468   return is_double() || is_int();
 469 }
 470
 471 bool Value::GetAsString(std::string* out_value) const {
 472   if (out_value && is_string()) {
 473     *out_value = string_value_;
 474     return true;
 475   }
 476   return is_string();
 477 }
 478
 479 bool Value::GetAsString(string16* out_value) const {
 480   if (out_value && is_string()) {
 481     *out_value = UTF8ToUTF16(string_value_);
 482     return true;
 483   }
 484   return is_string();
 485 }
 486
 487 bool Value::GetAsString(const Value** out_value) const {
 488   if (out_value && is_string()) {
 489     *out_value = static_cast<const Value*>(this);
 490     return true;
 491   }
 492   return is_string();
 493 }
 494
 495 bool Value::GetAsString(StringPiece* out_value) const {
 496   if (out_value && is_string()) {
 497     *out_value = string_value_;
 498     return true;
 499   }
 500   return is_string();
 501 }
 502
 503 bool Value::GetAsList(ListValue** out_value) {
 504   if (out_value && is_list()) {
 505     *out_value = static_cast<ListValue*>(this);
 506     return true;
 507   }
 508   return is_list();
 509 }
 510
 511 bool Value::GetAsList(const ListValue** out_value) const {
 512   if (out_value && is_list()) {
 513     *out_value = static_cast<const ListValue*>(this);
 514     return true;
 515   }
 516   return is_list();
 517 }
 518
 519 bool Value::GetAsDictionary(DictionaryValue** out_value) {
 520   if (out_value && is_dict()) {
 521     *out_value = static_cast<DictionaryValue*>(this);
 522     return true;
 523   }
 524   return is_dict();
 525 }
 526
 527 bool Value::GetAsDictionary(const DictionaryValue** out_value) const {
 528   if (out_value && is_dict()) {
 529     *out_value = static_cast<const DictionaryValue*>(this);
 530     return true;
 531   }
 532   return is_dict();
 533 }
 534
 535 Value* Value::DeepCopy() const {
 536   return new Value(Clone());
 537 }
 538
 539 std::unique_ptr<Value> Value::CreateDeepCopy() const {
 540   return std::make_unique<Value>(Clone());
 541 }
 542
 543 bool operator==(const Value& lhs, const Value& rhs) {
 544   if (lhs.type_ != rhs.type_)
 545     return false;
 546
 547   switch (lhs.type_) {
 548     case Value::Type::NONE:
 549       return true;
 550     case Value::Type::BOOLEAN:
 551       return lhs.bool_value_ == rhs.bool_value_;
 552     case Value::Type::INTEGER:
 553       return lhs.int_value_ == rhs.int_value_;
 554     case Value::Type::DOUBLE:
 555       return lhs.double_value_ == rhs.double_value_;
 556     case Value::Type::STRING:
 557       return lhs.string_value_ == rhs.string_value_;
 558     case Value::Type::BINARY:
 559       return lhs.binary_value_ == rhs.binary_value_;
 560     // TODO(crbug.com/646113): Clean this up when DictionaryValue and ListValue
 561     // are completely inlined.
 562     case Value::Type::DICTIONARY:
 563       if (lhs.dict_.size() != rhs.dict_.size())
 564         return false;
 565       return std::equal(std::begin(lhs.dict_), std::end(lhs.dict_),
 566                         std::begin(rhs.dict_),
 567                         [](const auto& u, const auto& v) {
 568                           return std::tie(u.first, *u.second) ==
 569                                  std::tie(v.first, *v.second);
 570                         });
 571     case Value::Type::LIST:
 572       return lhs.list_ == rhs.list_;
 573   }
 574
 575   NOTREACHED();
 576   return false;
 577 }
 578
 579 bool operator!=(const Value& lhs, const Value& rhs) {
 580   return !(lhs == rhs);
 581 }
 582
 583 bool operator<(const Value& lhs, const Value& rhs) {
 584   if (lhs.type_ != rhs.type_)
 585     return lhs.type_ < rhs.type_;
 586
 587   switch (lhs.type_) {
 588     case Value::Type::NONE:
 589       return false;
 590     case Value::Type::BOOLEAN:
 591       return lhs.bool_value_ < rhs.bool_value_;
 592     case Value::Type::INTEGER:
 593       return lhs.int_value_ < rhs.int_value_;
 594     case Value::Type::DOUBLE:
 595       return lhs.double_value_ < rhs.double_value_;
 596     case Value::Type::STRING:
 597       return lhs.string_value_ < rhs.string_value_;
 598     case Value::Type::BINARY:
 599       return lhs.binary_value_ < rhs.binary_value_;
 600     // TODO(crbug.com/646113): Clean this up when DictionaryValue and ListValue
 601     // are completely inlined.
 602     case Value::Type::DICTIONARY:
 603       return std::lexicographical_compare(
 604           std::begin(lhs.dict_), std::end(lhs.dict_), std::begin(rhs.dict_),
 605           std::end(rhs.dict_),
 606           [](const Value::DictStorage::value_type& u,
 607              const Value::DictStorage::value_type& v) {
 608             return std::tie(u.first, *u.second) < std::tie(v.first, *v.second);
 609           });
 610     case Value::Type::LIST:
 611       return lhs.list_ < rhs.list_;
 612   }
 613
 614   NOTREACHED();
 615   return false;
 616 }
 617
 618 bool operator>(const Value& lhs, const Value& rhs) {
 619   return rhs < lhs;
 620 }
 621
 622 bool operator<=(const Value& lhs, const Value& rhs) {
 623   return !(rhs < lhs);
 624 }
 625
 626 bool operator>=(const Value& lhs, const Value& rhs) {
 627   return !(lhs < rhs);
 628 }
 629
 630 bool Value::Equals(const Value* other) const {
 631   DCHECK(other);
 632   return *this == *other;
 633 }
 634
 635 size_t Value::EstimateMemoryUsage() const {
 636   switch (type_) {
 637     case Type::STRING:
 638       return base::trace_event::EstimateMemoryUsage(string_value_);
 639     case Type::BINARY:
 640       return base::trace_event::EstimateMemoryUsage(binary_value_);
 641     case Type::DICTIONARY:
 642       return base::trace_event::EstimateMemoryUsage(dict_);
 643     case Type::LIST:
 644       return base::trace_event::EstimateMemoryUsage(list_);
 645     default:
 646       return 0;
 647   }
 648 }
 649
 650 void Value::InternalMoveConstructFrom(Value&& that) {
 651   type_ = that.type_;
 652
 653   switch (type_) {
 654     case Type::NONE:
 655       return;
 656     case Type::BOOLEAN:
 657       bool_value_ = that.bool_value_;
 658       return;
 659     case Type::INTEGER:
 660       int_value_ = that.int_value_;
 661       return;
 662     case Type::DOUBLE:
 663       double_value_ = that.double_value_;
 664       return;
 665     case Type::STRING:
 666       new (&string_value_) std::string(std::move(that.string_value_));
 667       return;
 668     case Type::BINARY:
 669       new (&binary_value_) BlobStorage(std::move(that.binary_value_));
 670       return;
 671     case Type::DICTIONARY:
 672       new (&dict_) DictStorage(std::move(that.dict_));
 673       return;
 674     case Type::LIST:
 675       new (&list_) ListStorage(std::move(that.list_));
 676       return;
 677   }
 678 }
 679
 680 void Value::InternalCleanup() {
 681   switch (type_) {
 682     case Type::NONE:
 683     case Type::BOOLEAN:
 684     case Type::INTEGER:
 685     case Type::DOUBLE:
 686       // Nothing to do
 687       return;
 688
 689     case Type::STRING:
 690       string_value_.~basic_string();
 691       return;
 692     case Type::BINARY:
 693       binary_value_.~BlobStorage();
 694       return;
 695     case Type::DICTIONARY:
 696       dict_.~DictStorage();
 697       return;
 698     case Type::LIST:
 699       list_.~ListStorage();
 700       return;
 701   }
 702 }
 703
 704 ///////////////////// DictionaryValue ////////////////////
 705
 706 // static
 707 std::unique_ptr<DictionaryValue> DictionaryValue::From(
 708     std::unique_ptr<Value> value) {
 709   DictionaryValue* out;
 710   if (value && value->GetAsDictionary(&out)) {
 711     ignore_result(value.release());
 712     return WrapUnique(out);
 713   }
 714   return nullptr;
 715 }
 716
 717 DictionaryValue::DictionaryValue() : Value(Type::DICTIONARY) {}
 718 DictionaryValue::DictionaryValue(const DictStorage& in_dict) : Value(in_dict) {}
 719 DictionaryValue::DictionaryValue(DictStorage&& in_dict) noexcept
 720     : Value(std::move(in_dict)) {}
 721
 722 bool DictionaryValue::HasKey(StringPiece key) const {
 723   DCHECK(IsStringUTF8(key));
 724   auto current_entry = dict_.find(key);
 725   DCHECK((current_entry == dict_.end()) || current_entry->second);
 726   return current_entry != dict_.end();
 727 }
 728
 729 void DictionaryValue::Clear() {
 730   dict_.clear();
 731 }
 732
 733 Value* DictionaryValue::Set(StringPiece path, std::unique_ptr<Value> in_value) {
 734   DCHECK(IsStringUTF8(path));
 735   DCHECK(in_value);
 736
 737   StringPiece current_path(path);
 738   Value* current_dictionary = this;
 739   for (size_t delimiter_position = current_path.find('.');
 740        delimiter_position != StringPiece::npos;
 741        delimiter_position = current_path.find('.')) {
 742     // Assume that we're indexing into a dictionary.
 743     StringPiece key = current_path.substr(0, delimiter_position);
 744     Value* child_dictionary =
 745         current_dictionary->FindKeyOfType(key, Type::DICTIONARY);
 746     if (!child_dictionary) {
 747       child_dictionary =
 748           current_dictionary->SetKey(key, Value(Type::DICTIONARY));
 749     }
 750
 751     current_dictionary = child_dictionary;
 752     current_path = current_path.substr(delimiter_position + 1);
 753   }
 754
 755   return static_cast<DictionaryValue*>(current_dictionary)
 756       ->SetWithoutPathExpansion(current_path, std::move(in_value));
 757 }
 758
 759 Value* DictionaryValue::SetBoolean(StringPiece path, bool in_value) {
 760   return Set(path, std::make_unique<Value>(in_value));
 761 }
 762
 763 Value* DictionaryValue::SetInteger(StringPiece path, int in_value) {
 764   return Set(path, std::make_unique<Value>(in_value));
 765 }
 766
 767 Value* DictionaryValue::SetDouble(StringPiece path, double in_value) {
 768   return Set(path, std::make_unique<Value>(in_value));
 769 }
 770
 771 Value* DictionaryValue::SetString(StringPiece path, StringPiece in_value) {
 772   return Set(path, std::make_unique<Value>(in_value));
 773 }
 774
 775 Value* DictionaryValue::SetString(StringPiece path, const string16& in_value) {
 776   return Set(path, std::make_unique<Value>(in_value));
 777 }
 778
 779 DictionaryValue* DictionaryValue::SetDictionary(
 780     StringPiece path,
 781     std::unique_ptr<DictionaryValue> in_value) {
 782   return static_cast<DictionaryValue*>(Set(path, std::move(in_value)));
 783 }
 784
 785 ListValue* DictionaryValue::SetList(StringPiece path,
 786                                     std::unique_ptr<ListValue> in_value) {
 787   return static_cast<ListValue*>(Set(path, std::move(in_value)));
 788 }
 789
 790 Value* DictionaryValue::SetWithoutPathExpansion(
 791     StringPiece key,
 792     std::unique_ptr<Value> in_value) {
 793   // NOTE: We can't use |insert_or_assign| here, as only |try_emplace| does
 794   // an explicit conversion from StringPiece to std::string if necessary.
 795   auto result = dict_.try_emplace(key, std::move(in_value));
 796   if (!result.second) {
 797     // in_value is guaranteed to be still intact at this point.
 798     result.first->second = std::move(in_value);
 799   }
 800   return result.first->second.get();
 801 }
 802
 803 bool DictionaryValue::Get(StringPiece path,
 804                           const Value** out_value) const {
 805   DCHECK(IsStringUTF8(path));
 806   StringPiece current_path(path);
 807   const DictionaryValue* current_dictionary = this;
 808   for (size_t delimiter_position = current_path.find('.');
 809        delimiter_position != std::string::npos;
 810        delimiter_position = current_path.find('.')) {
 811     const DictionaryValue* child_dictionary = nullptr;
 812     if (!current_dictionary->GetDictionaryWithoutPathExpansion(
 813             current_path.substr(0, delimiter_position), &child_dictionary)) {
 814       return false;
 815     }
 816
 817     current_dictionary = child_dictionary;
 818     current_path = current_path.substr(delimiter_position + 1);
 819   }
 820
 821   return current_dictionary->GetWithoutPathExpansion(current_path, out_value);
 822 }
 823
 824 bool DictionaryValue::Get(StringPiece path, Value** out_value)  {
 825   return static_cast<const DictionaryValue&>(*this).Get(
 826       path,
 827       const_cast<const Value**>(out_value));
 828 }
 829
 830 bool DictionaryValue::GetBoolean(StringPiece path, bool* bool_value) const {
 831   const Value* value;
 832   if (!Get(path, &value))
 833     return false;
 834
 835   return value->GetAsBoolean(bool_value);
 836 }
 837
 838 bool DictionaryValue::GetInteger(StringPiece path, int* out_value) const {
 839   const Value* value;
 840   if (!Get(path, &value))
 841     return false;
 842
 843   return value->GetAsInteger(out_value);
 844 }
 845
 846 bool DictionaryValue::GetDouble(StringPiece path, double* out_value) const {
 847   const Value* value;
 848   if (!Get(path, &value))
 849     return false;
 850
 851   return value->GetAsDouble(out_value);
 852 }
 853
 854 bool DictionaryValue::GetString(StringPiece path,
 855                                 std::string* out_value) const {
 856   const Value* value;
 857   if (!Get(path, &value))
 858     return false;
 859
 860   return value->GetAsString(out_value);
 861 }
 862
 863 bool DictionaryValue::GetString(StringPiece path, string16* out_value) const {
 864   const Value* value;
 865   if (!Get(path, &value))
 866     return false;
 867
 868   return value->GetAsString(out_value);
 869 }
 870
 871 bool DictionaryValue::GetStringASCII(StringPiece path,
 872                                      std::string* out_value) const {
 873   std::string out;
 874   if (!GetString(path, &out))
 875     return false;
 876
 877   if (!IsStringASCII(out)) {
 878     NOTREACHED();
 879     return false;
 880   }
 881
 882   out_value->assign(out);
 883   return true;
 884 }
 885
 886 bool DictionaryValue::GetBinary(StringPiece path,
 887                                 const Value** out_value) const {
 888   const Value* value;
 889   bool result = Get(path, &value);
 890   if (!result || !value->is_blob())
 891     return false;
 892
 893   if (out_value)
 894     *out_value = value;
 895
 896   return true;
 897 }
 898
 899 bool DictionaryValue::GetBinary(StringPiece path, Value** out_value) {
 900   return static_cast<const DictionaryValue&>(*this).GetBinary(
 901       path, const_cast<const Value**>(out_value));
 902 }
 903
 904 bool DictionaryValue::GetDictionary(StringPiece path,
 905                                     const DictionaryValue** out_value) const {
 906   const Value* value;
 907   bool result = Get(path, &value);
 908   if (!result || !value->is_dict())
 909     return false;
 910
 911   if (out_value)
 912     *out_value = static_cast<const DictionaryValue*>(value);
 913
 914   return true;
 915 }
 916
 917 bool DictionaryValue::GetDictionary(StringPiece path,
 918                                     DictionaryValue** out_value) {
 919   return static_cast<const DictionaryValue&>(*this).GetDictionary(
 920       path,
 921       const_cast<const DictionaryValue**>(out_value));
 922 }
 923
 924 bool DictionaryValue::GetList(StringPiece path,
 925                               const ListValue** out_value) const {
 926   const Value* value;
 927   bool result = Get(path, &value);
 928   if (!result || !value->is_list())
 929     return false;
 930
 931   if (out_value)
 932     *out_value = static_cast<const ListValue*>(value);
 933
 934   return true;
 935 }
 936
 937 bool DictionaryValue::GetList(StringPiece path, ListValue** out_value) {
 938   return static_cast<const DictionaryValue&>(*this).GetList(
 939       path,
 940       const_cast<const ListValue**>(out_value));
 941 }
 942
 943 bool DictionaryValue::GetWithoutPathExpansion(StringPiece key,
 944                                               const Value** out_value) const {
 945   DCHECK(IsStringUTF8(key));
 946   auto entry_iterator = dict_.find(key);
 947   if (entry_iterator == dict_.end())
 948     return false;
 949
 950   if (out_value)
 951     *out_value = entry_iterator->second.get();
 952   return true;
 953 }
 954
 955 bool DictionaryValue::GetWithoutPathExpansion(StringPiece key,
 956                                               Value** out_value) {
 957   return static_cast<const DictionaryValue&>(*this).GetWithoutPathExpansion(
 958       key,
 959       const_cast<const Value**>(out_value));
 960 }
 961
 962 bool DictionaryValue::GetBooleanWithoutPathExpansion(StringPiece key,
 963                                                      bool* out_value) const {
 964   const Value* value;
 965   if (!GetWithoutPathExpansion(key, &value))
 966     return false;
 967
 968   return value->GetAsBoolean(out_value);
 969 }
 970
 971 bool DictionaryValue::GetIntegerWithoutPathExpansion(StringPiece key,
 972                                                      int* out_value) const {
 973   const Value* value;
 974   if (!GetWithoutPathExpansion(key, &value))
 975     return false;
 976
 977   return value->GetAsInteger(out_value);
 978 }
 979
 980 bool DictionaryValue::GetDoubleWithoutPathExpansion(StringPiece key,
 981                                                     double* out_value) const {
 982   const Value* value;
 983   if (!GetWithoutPathExpansion(key, &value))
 984     return false;
 985
 986   return value->GetAsDouble(out_value);
 987 }
 988
 989 bool DictionaryValue::GetStringWithoutPathExpansion(
 990     StringPiece key,
 991     std::string* out_value) const {
 992   const Value* value;
 993   if (!GetWithoutPathExpansion(key, &value))
 994     return false;
 995
 996   return value->GetAsString(out_value);
 997 }
 998
 999 bool DictionaryValue::GetStringWithoutPathExpansion(StringPiece key,
1000                                                     string16* out_value) const {
1001   const Value* value;
1002   if (!GetWithoutPathExpansion(key, &value))
1003     return false;
1004
1005   return value->GetAsString(out_value);
1006 }
1007
1008 bool DictionaryValue::GetDictionaryWithoutPathExpansion(
1009     StringPiece key,
1010     const DictionaryValue** out_value) const {
1011   const Value* value;
1012   bool result = GetWithoutPathExpansion(key, &value);
1013   if (!result || !value->is_dict())
1014     return false;
1015
1016   if (out_value)
1017     *out_value = static_cast<const DictionaryValue*>(value);
1018
1019   return true;
1020 }
1021
1022 bool DictionaryValue::GetDictionaryWithoutPathExpansion(
1023     StringPiece key,
1024     DictionaryValue** out_value) {
1025   const DictionaryValue& const_this =
1026       static_cast<const DictionaryValue&>(*this);
1027   return const_this.GetDictionaryWithoutPathExpansion(
1028           key,
1029           const_cast<const DictionaryValue**>(out_value));
1030 }
1031
1032 bool DictionaryValue::GetListWithoutPathExpansion(
1033     StringPiece key,
1034     const ListValue** out_value) const {
1035   const Value* value;
1036   bool result = GetWithoutPathExpansion(key, &value);
1037   if (!result || !value->is_list())
1038     return false;
1039
1040   if (out_value)
1041     *out_value = static_cast<const ListValue*>(value);
1042
1043   return true;
1044 }
1045
1046 bool DictionaryValue::GetListWithoutPathExpansion(StringPiece key,
1047                                                   ListValue** out_value) {
1048   return
1049       static_cast<const DictionaryValue&>(*this).GetListWithoutPathExpansion(
1050           key,
1051           const_cast<const ListValue**>(out_value));
1052 }
1053
1054 bool DictionaryValue::Remove(StringPiece path,
1055                              std::unique_ptr<Value>* out_value) {
1056   DCHECK(IsStringUTF8(path));
1057   StringPiece current_path(path);
1058   DictionaryValue* current_dictionary = this;
1059   size_t delimiter_position = current_path.rfind('.');
1060   if (delimiter_position != StringPiece::npos) {
1061     if (!GetDictionary(current_path.substr(0, delimiter_position),
1062                        &current_dictionary))
1063       return false;
1064     current_path = current_path.substr(delimiter_position + 1);
1065   }
1066
1067   return current_dictionary->RemoveWithoutPathExpansion(current_path,
1068                                                         out_value);
1069 }
1070
1071 bool DictionaryValue::RemoveWithoutPathExpansion(
1072     StringPiece key,
1073     std::unique_ptr<Value>* out_value) {
1074   DCHECK(IsStringUTF8(key));
1075   auto entry_iterator = dict_.find(key);
1076   if (entry_iterator == dict_.end())
1077     return false;
1078
1079   if (out_value)
1080     *out_value = std::move(entry_iterator->second);
1081   dict_.erase(entry_iterator);
1082   return true;
1083 }
1084
1085 bool DictionaryValue::RemovePath(StringPiece path,
1086                                  std::unique_ptr<Value>* out_value) {
1087   bool result = false;
1088   size_t delimiter_position = path.find('.');
1089
1090   if (delimiter_position == std::string::npos)
1091     return RemoveWithoutPathExpansion(path, out_value);
1092
1093   StringPiece subdict_path = path.substr(0, delimiter_position);
1094   DictionaryValue* subdict = nullptr;
1095   if (!GetDictionary(subdict_path, &subdict))
1096     return false;
1097   result = subdict->RemovePath(path.substr(delimiter_position + 1),
1098                                out_value);
1099   if (result && subdict->empty())
1100     RemoveWithoutPathExpansion(subdict_path, nullptr);
1101
1102   return result;
1103 }
1104
1105 std::unique_ptr<DictionaryValue> DictionaryValue::DeepCopyWithoutEmptyChildren()
1106     const {
1107   std::unique_ptr<DictionaryValue> copy =
1108       CopyDictionaryWithoutEmptyChildren(*this);
1109   if (!copy)
1110     copy = std::make_unique<DictionaryValue>();
1111   return copy;
1112 }
1113
1114 void DictionaryValue::MergeDictionary(const DictionaryValue* dictionary) {
1115   CHECK(dictionary->is_dict());
1116   for (DictionaryValue::Iterator it(*dictionary); !it.IsAtEnd(); it.Advance()) {
1117     const Value* merge_value = &it.value();
1118     // Check whether we have to merge dictionaries.
1119     if (merge_value->is_dict()) {
1120       DictionaryValue* sub_dict;
1121       if (GetDictionaryWithoutPathExpansion(it.key(), &sub_dict)) {
1122         sub_dict->MergeDictionary(
1123             static_cast<const DictionaryValue*>(merge_value));
1124         continue;
1125       }
1126     }
1127     // All other cases: Make a copy and hook it up.
1128     SetKey(it.key(), merge_value->Clone());
1129   }
1130 }
1131
1132 void DictionaryValue::Swap(DictionaryValue* other) {
1133   CHECK(other->is_dict());
1134   dict_.swap(other->dict_);
1135 }
1136
1137 DictionaryValue::Iterator::Iterator(const DictionaryValue& target)
1138     : target_(target), it_(target.dict_.begin()) {}
1139
1140 DictionaryValue::Iterator::Iterator(const Iterator& other) = default;
1141
1142 DictionaryValue::Iterator::~Iterator() = default;
1143
1144 DictionaryValue* DictionaryValue::DeepCopy() const {
1145   return new DictionaryValue(dict_);
1146 }
1147
1148 std::unique_ptr<DictionaryValue> DictionaryValue::CreateDeepCopy() const {
1149   return std::make_unique<DictionaryValue>(dict_);
1150 }
1151
1152 ///////////////////// ListValue ////////////////////
1153
1154 // static
1155 std::unique_ptr<ListValue> ListValue::From(std::unique_ptr<Value> value) {
1156   ListValue* out;
1157   if (value && value->GetAsList(&out)) {
1158     ignore_result(value.release());
1159     return WrapUnique(out);
1160   }
1161   return nullptr;
1162 }
1163
1164 ListValue::ListValue() : Value(Type::LIST) {}
1165 ListValue::ListValue(const ListStorage& in_list) : Value(in_list) {}
1166 ListValue::ListValue(ListStorage&& in_list) noexcept
1167     : Value(std::move(in_list)) {}
1168
1169 void ListValue::Clear() {
1170   list_.clear();
1171 }
1172
1173 void ListValue::Reserve(size_t n) {
1174   list_.reserve(n);
1175 }
1176
1177 bool ListValue::Set(size_t index, std::unique_ptr<Value> in_value) {
1178   if (!in_value)
1179     return false;
1180
1181   if (index >= list_.size())
1182     list_.resize(index + 1);
1183
1184   list_[index] = std::move(*in_value);
1185   return true;
1186 }
1187
1188 bool ListValue::Get(size_t index, const Value** out_value) const {
1189   if (index >= list_.size())
1190     return false;
1191
1192   if (out_value)
1193     *out_value = &list_[index];
1194
1195   return true;
1196 }
1197
1198 bool ListValue::Get(size_t index, Value** out_value) {
1199   return static_cast<const ListValue&>(*this).Get(
1200       index,
1201       const_cast<const Value**>(out_value));
1202 }
1203
1204 bool ListValue::GetBoolean(size_t index, bool* bool_value) const {
1205   const Value* value;
1206   if (!Get(index, &value))
1207     return false;
1208
1209   return value->GetAsBoolean(bool_value);
1210 }
1211
1212 bool ListValue::GetInteger(size_t index, int* out_value) const {
1213   const Value* value;
1214   if (!Get(index, &value))
1215     return false;
1216
1217   return value->GetAsInteger(out_value);
1218 }
1219
1220 bool ListValue::GetDouble(size_t index, double* out_value) const {
1221   const Value* value;
1222   if (!Get(index, &value))
1223     return false;
1224
1225   return value->GetAsDouble(out_value);
1226 }
1227
1228 bool ListValue::GetString(size_t index, std::string* out_value) const {
1229   const Value* value;
1230   if (!Get(index, &value))
1231     return false;
1232
1233   return value->GetAsString(out_value);
1234 }
1235
1236 bool ListValue::GetString(size_t index, string16* out_value) const {
1237   const Value* value;
1238   if (!Get(index, &value))
1239     return false;
1240
1241   return value->GetAsString(out_value);
1242 }
1243
1244 bool ListValue::GetDictionary(size_t index,
1245                               const DictionaryValue** out_value) const {
1246   const Value* value;
1247   bool result = Get(index, &value);
1248   if (!result || !value->is_dict())
1249     return false;
1250
1251   if (out_value)
1252     *out_value = static_cast<const DictionaryValue*>(value);
1253
1254   return true;
1255 }
1256
1257 bool ListValue::GetDictionary(size_t index, DictionaryValue** out_value) {
1258   return static_cast<const ListValue&>(*this).GetDictionary(
1259       index,
1260       const_cast<const DictionaryValue**>(out_value));
1261 }
1262
1263 bool ListValue::GetList(size_t index, const ListValue** out_value) const {
1264   const Value* value;
1265   bool result = Get(index, &value);
1266   if (!result || !value->is_list())
1267     return false;
1268
1269   if (out_value)
1270     *out_value = static_cast<const ListValue*>(value);
1271
1272   return true;
1273 }
1274
1275 bool ListValue::GetList(size_t index, ListValue** out_value) {
1276   return static_cast<const ListValue&>(*this).GetList(
1277       index,
1278       const_cast<const ListValue**>(out_value));
1279 }
1280
1281 bool ListValue::Remove(size_t index, std::unique_ptr<Value>* out_value) {
1282   if (index >= list_.size())
1283     return false;
1284
1285   if (out_value)
1286     *out_value = std::make_unique<Value>(std::move(list_[index]));
1287
1288   list_.erase(list_.begin() + index);
1289   return true;
1290 }
1291
1292 bool ListValue::Remove(const Value& value, size_t* index) {
1293   auto it = std::find(list_.begin(), list_.end(), value);
1294
1295   if (it == list_.end())
1296     return false;
1297
1298   if (index)
1299     *index = std::distance(list_.begin(), it);
1300
1301   list_.erase(it);
1302   return true;
1303 }
1304
1305 ListValue::iterator ListValue::Erase(iterator iter,
1306                                      std::unique_ptr<Value>* out_value) {
1307   if (out_value)
1308     *out_value = std::make_unique<Value>(std::move(*iter));
1309
1310   return list_.erase(iter);
1311 }
1312
1313 void ListValue::Append(std::unique_ptr<Value> in_value) {
1314   list_.push_back(std::move(*in_value));
1315 }
1316
1317 void ListValue::AppendBoolean(bool in_value) {
1318   list_.emplace_back(in_value);
1319 }
1320
1321 void ListValue::AppendInteger(int in_value) {
1322   list_.emplace_back(in_value);
1323 }
1324
1325 void ListValue::AppendDouble(double in_value) {
1326   list_.emplace_back(in_value);
1327 }
1328
1329 void ListValue::AppendString(StringPiece in_value) {
1330   list_.emplace_back(in_value);
1331 }
1332
1333 void ListValue::AppendString(const string16& in_value) {
1334   list_.emplace_back(in_value);
1335 }
1336
1337 void ListValue::AppendStrings(const std::vector<std::string>& in_values) {
1338   list_.reserve(list_.size() + in_values.size());
1339   for (const auto& in_value : in_values)
1340     list_.emplace_back(in_value);
1341 }
1342
1343 void ListValue::AppendStrings(const std::vector<string16>& in_values) {
1344   list_.reserve(list_.size() + in_values.size());
1345   for (const auto& in_value : in_values)
1346     list_.emplace_back(in_value);
1347 }
1348
1349 bool ListValue::AppendIfNotPresent(std::unique_ptr<Value> in_value) {
1350   DCHECK(in_value);
1351   if (ContainsValue(list_, *in_value))
1352     return false;
1353
1354   list_.push_back(std::move(*in_value));
1355   return true;
1356 }
1357
1358 bool ListValue::Insert(size_t index, std::unique_ptr<Value> in_value) {
1359   DCHECK(in_value);
1360   if (index > list_.size())
1361     return false;
1362
1363   list_.insert(list_.begin() + index, std::move(*in_value));
1364   return true;
1365 }
1366
1367 ListValue::const_iterator ListValue::Find(const Value& value) const {
1368   return std::find(list_.begin(), list_.end(), value);
1369 }
1370
1371 void ListValue::Swap(ListValue* other) {
1372   CHECK(other->is_list());
1373   list_.swap(other->list_);
1374 }
1375
1376 ListValue* ListValue::DeepCopy() const {
1377   return new ListValue(list_);
1378 }
1379
1380 std::unique_ptr<ListValue> ListValue::CreateDeepCopy() const {
1381   return std::make_unique<ListValue>(list_);
1382 }
1383
1384 ValueSerializer::~ValueSerializer() = default;
1385
1386 ValueDeserializer::~ValueDeserializer() = default;
1387
1388 std::ostream& operator<<(std::ostream& out, const Value& value) {
1389   std::string json;
1390   JSONWriter::WriteWithOptions(value, JSONWriter::OPTIONS_PRETTY_PRINT, &json);
1391   return out << json;
1392 }
1393
1394 std::ostream& operator<<(std::ostream& out, const Value::Type& type) {
1395   if (static_cast<int>(type) < 0 ||
1396       static_cast<size_t>(type) >= arraysize(kTypeNames))
1397     return out << "Invalid Type (index = " << static_cast<int>(type) << ")";
1398   return out << Value::GetTypeName(type);
1399 }
1400
1401 }  // namespace base