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/bit_cast.h"
  16 #include "base/check_op.h"
  17 #include "base/containers/checked_iterators.h"
  18 #include "base/json/json_writer.h"
  19 #include "base/memory/ptr_util.h"
  20 #include "base/notreached.h"
  21 #include "base/stl_util.h"
  22 #include "base/strings/string_util.h"
  23 #include "base/strings/utf_string_conversions.h"
  24 #include "base/tracing_buildflags.h"
  25
  26 #if BUILDFLAG(ENABLE_BASE_TRACING)
  27 #include "base/trace_event/memory_usage_estimator.h"
  28 #endif  // BUILDFLAG(ENABLE_BASE_TRACING)
  29
  30 namespace base {
  31
  32 // base::Value must be standard layout to guarantee that writing to
  33 // |bool_type_| then reading |type_| is defined behaviour. See:
  34 //
  35 // [class.union]:
  36 //   If a standard-layout union contains several standard-layout structs that
  37 //   share a common initial sequence (9.2), and if an object of this
  38 //   standard-layout union type contains one of the standard-layout structs,
  39 //   it is permitted to inspect the common initial sequence of any of
  40 //   standard-layout struct members;
  41 //
  42 static_assert(std::is_standard_layout<Value>::value,
  43               "base::Value should be a standard-layout C++ class in order "
  44               "to avoid undefined behaviour in its implementation!");
  45
  46 static_assert(sizeof(Value::DoubleStorage) == sizeof(double),
  47               "The double and DoubleStorage types should have the same size");
  48
  49 namespace {
  50
  51 const char* const kTypeNames[] = {"null",   "boolean", "integer",    "double",
  52                                   "string", "binary",  "dictionary", "list"};
  53 static_assert(base::size(kTypeNames) ==
  54                   static_cast<size_t>(Value::Type::LIST) + 1,
  55               "kTypeNames Has Wrong Size");
  56
  57 std::unique_ptr<Value> CopyWithoutEmptyChildren(const Value& node);
  58
  59 // Make a deep copy of |node|, but don't include empty lists or dictionaries
  60 // in the copy. It's possible for this function to return NULL and it
  61 // expects |node| to always be non-NULL.
  62 std::unique_ptr<Value> CopyListWithoutEmptyChildren(const Value& list) {
  63   Value copy(Value::Type::LIST);
  64   for (const auto& entry : list.GetList()) {
  65     std::unique_ptr<Value> child_copy = CopyWithoutEmptyChildren(entry);
  66     if (child_copy)
  67       copy.Append(std::move(*child_copy));
  68   }
  69   return copy.GetList().empty() ? nullptr
  70                                 : std::make_unique<Value>(std::move(copy));
  71 }
  72
  73 std::unique_ptr<DictionaryValue> CopyDictionaryWithoutEmptyChildren(
  74     const DictionaryValue& dict) {
  75   std::unique_ptr<DictionaryValue> copy;
  76   for (const auto& it : dict.DictItems()) {
  77     std::unique_ptr<Value> child_copy = CopyWithoutEmptyChildren(it.second);
  78     if (child_copy) {
  79       if (!copy)
  80         copy = std::make_unique<DictionaryValue>();
  81       copy->SetKey(it.first, std::move(*child_copy));
  82     }
  83   }
  84   return copy;
  85 }
  86
  87 std::unique_ptr<Value> CopyWithoutEmptyChildren(const Value& node) {
  88   switch (node.type()) {
  89     case Value::Type::LIST:
  90       return CopyListWithoutEmptyChildren(static_cast<const ListValue&>(node));
  91
  92     case Value::Type::DICTIONARY:
  93       return CopyDictionaryWithoutEmptyChildren(
  94           static_cast<const DictionaryValue&>(node));
  95
  96     default:
  97       return std::make_unique<Value>(node.Clone());
  98   }
  99 }
 100
 101 // Helper class to enumerate the path components from a StringPiece
 102 // without performing heap allocations. Components are simply separated
 103 // by single dots (e.g. "foo.bar.baz"  -> ["foo", "bar", "baz"]).
 104 //
 105 // Usage example:
 106 //    PathSplitter splitter(some_path);
 107 //    while (splitter.HasNext()) {
 108 //       StringPiece component = splitter.Next();
 109 //       ...
 110 //    }
 111 //
 112 class PathSplitter {
 113  public:
 114   explicit PathSplitter(StringPiece path) : path_(path) {}
 115
 116   bool HasNext() const { return pos_ < path_.size(); }
 117
 118   StringPiece Next() {
 119     DCHECK(HasNext());
 120     size_t start = pos_;
 121     size_t pos = path_.find('.', start);
 122     size_t end;
 123     if (pos == path_.npos) {
 124       end = path_.size();
 125       pos_ = end;
 126     } else {
 127       end = pos;
 128       pos_ = pos + 1;
 129     }
 130     return path_.substr(start, end - start);
 131   }
 132
 133  private:
 134   StringPiece path_;
 135   size_t pos_ = 0;
 136 };
 137
 138 }  // namespace
 139
 140 // static
 141 std::unique_ptr<Value> Value::CreateWithCopiedBuffer(const char* buffer,
 142                                                      size_t size) {
 143   return std::make_unique<Value>(BlobStorage(buffer, buffer + size));
 144 }
 145
 146 // static
 147 Value Value::FromUniquePtrValue(std::unique_ptr<Value> val) {
 148   return std::move(*val);
 149 }
 150
 151 // static
 152 std::unique_ptr<Value> Value::ToUniquePtrValue(Value val) {
 153   return std::make_unique<Value>(std::move(val));
 154 }
 155
 156 // static
 157 const DictionaryValue& Value::AsDictionaryValue(const Value& val) {
 158   CHECK(val.is_dict());
 159   return static_cast<const DictionaryValue&>(val);
 160 }
 161
 162 // static
 163 const ListValue& Value::AsListValue(const Value& val) {
 164   CHECK(val.is_list());
 165   return static_cast<const ListValue&>(val);
 166 }
 167
 168 Value::Value(Value&& that) noexcept {
 169   InternalMoveConstructFrom(std::move(that));
 170 }
 171
 172 Value::Value(Type type) : type_(type) {
 173   // Initialize with the default value.
 174   switch (type_) {
 175     case Type::NONE:
 176       return;
 177
 178     case Type::BOOLEAN:
 179       bool_value_ = false;
 180       return;
 181     case Type::INTEGER:
 182       int_value_ = 0;
 183       return;
 184     case Type::DOUBLE:
 185       double_value_ = bit_cast<DoubleStorage>(0.0);
 186       return;
 187     case Type::STRING:
 188       new (&string_value_) std::string();
 189       return;
 190     case Type::BINARY:
 191       new (&binary_value_) BlobStorage();
 192       return;
 193     case Type::DICTIONARY:
 194       new (&dict_) DictStorage();
 195       return;
 196     case Type::LIST:
 197       new (&list_) ListStorage();
 198       return;
 199     // TODO(crbug.com/859477): Remove after root cause is found.
 200     case Type::DEAD:
 201       CHECK(false);
 202       return;
 203   }
 204
 205   // TODO(crbug.com/859477): Revert to NOTREACHED() after root cause is found.
 206   CHECK(false);
 207 }
 208
 209 Value::Value(bool in_bool) : type_(Type::BOOLEAN), bool_value_(in_bool) {}
 210
 211 Value::Value(int in_int) : type_(Type::INTEGER), int_value_(in_int) {}
 212
 213 Value::Value(double in_double)
 214     : type_(Type::DOUBLE), double_value_(bit_cast<DoubleStorage>(in_double)) {
 215   if (!std::isfinite(in_double)) {
 216     NOTREACHED() << "Non-finite (i.e. NaN or positive/negative infinity) "
 217                  << "values cannot be represented in JSON";
 218     double_value_ = bit_cast<DoubleStorage>(0.0);
 219   }
 220 }
 221
 222 Value::Value(const char* in_string) : Value(std::string(in_string)) {}
 223
 224 Value::Value(StringPiece in_string) : Value(std::string(in_string)) {}
 225
 226 Value::Value(std::string&& in_string) noexcept
 227     : type_(Type::STRING), string_value_(std::move(in_string)) {
 228   DCHECK(IsStringUTF8AllowingNoncharacters(string_value_));
 229 }
 230
 231 Value::Value(const char16* in_string16) : Value(StringPiece16(in_string16)) {}
 232
 233 Value::Value(StringPiece16 in_string16) : Value(UTF16ToUTF8(in_string16)) {}
 234
 235 Value::Value(const std::vector<char>& in_blob)
 236     : type_(Type::BINARY), binary_value_(in_blob.begin(), in_blob.end()) {}
 237
 238 Value::Value(base::span<const uint8_t> in_blob)
 239     : type_(Type::BINARY), binary_value_(in_blob.begin(), in_blob.end()) {}
 240
 241 Value::Value(BlobStorage&& in_blob) noexcept
 242     : type_(Type::BINARY), binary_value_(std::move(in_blob)) {}
 243
 244 Value::Value(const DictStorage& in_dict) : type_(Type::DICTIONARY), dict_() {
 245   dict_.reserve(in_dict.size());
 246   for (const auto& it : in_dict) {
 247     dict_.try_emplace(dict_.end(), it.first,
 248                       std::make_unique<Value>(it.second->Clone()));
 249   }
 250 }
 251
 252 Value::Value(DictStorage&& in_dict) noexcept
 253     : type_(Type::DICTIONARY), dict_(std::move(in_dict)) {}
 254
 255 Value::Value(span<const Value> in_list) : type_(Type::LIST), list_() {
 256   list_.reserve(in_list.size());
 257   for (const auto& val : in_list)
 258     list_.emplace_back(val.Clone());
 259 }
 260
 261 Value::Value(ListStorage&& in_list) noexcept
 262     : type_(Type::LIST), list_(std::move(in_list)) {}
 263
 264 Value& Value::operator=(Value&& that) noexcept {
 265   InternalCleanup();
 266   InternalMoveConstructFrom(std::move(that));
 267
 268   return *this;
 269 }
 270
 271 double Value::AsDoubleInternal() const {
 272   return bit_cast<double>(double_value_);
 273 }
 274
 275 Value Value::Clone() const {
 276   switch (type_) {
 277     case Type::NONE:
 278       return Value();
 279     case Type::BOOLEAN:
 280       return Value(bool_value_);
 281     case Type::INTEGER:
 282       return Value(int_value_);
 283     case Type::DOUBLE:
 284       return Value(AsDoubleInternal());
 285     case Type::STRING:
 286       return Value(string_value_);
 287     case Type::BINARY:
 288       return Value(binary_value_);
 289     case Type::DICTIONARY:
 290       return Value(dict_);
 291     case Type::LIST:
 292       return Value(list_);
 293       // TODO(crbug.com/859477): Remove after root cause is found.
 294     case Type::DEAD:
 295       CHECK(false);
 296       return Value();
 297   }
 298
 299   // TODO(crbug.com/859477): Revert to NOTREACHED() after root cause is found.
 300   CHECK(false);
 301   return Value();
 302 }
 303
 304 Value::~Value() {
 305   InternalCleanup();
 306   // TODO(crbug.com/859477): Remove after root cause is found.
 307   type_ = Type::DEAD;
 308 }
 309
 310 // static
 311 const char* Value::GetTypeName(Value::Type type) {
 312   DCHECK_GE(static_cast<int>(type), 0);
 313   DCHECK_LT(static_cast<size_t>(type), base::size(kTypeNames));
 314   return kTypeNames[static_cast<size_t>(type)];
 315 }
 316
 317 bool Value::GetBool() const {
 318   CHECK(is_bool());
 319   return bool_value_;
 320 }
 321
 322 int Value::GetInt() const {
 323   CHECK(is_int());
 324   return int_value_;
 325 }
 326
 327 double Value::GetDouble() const {
 328   if (is_double())
 329     return AsDoubleInternal();
 330   if (is_int())
 331     return int_value_;
 332   CHECK(false);
 333   return 0.0;
 334 }
 335
 336 const std::string& Value::GetString() const {
 337   CHECK(is_string());
 338   return string_value_;
 339 }
 340
 341 std::string& Value::GetString() {
 342   CHECK(is_string());
 343   return string_value_;
 344 }
 345
 346 const Value::BlobStorage& Value::GetBlob() const {
 347   CHECK(is_blob());
 348   return binary_value_;
 349 }
 350
 351 Value::ListView Value::GetList() {
 352   CHECK(is_list());
 353   return list_;
 354 }
 355
 356 Value::ConstListView Value::GetList() const {
 357   CHECK(is_list());
 358   return list_;
 359 }
 360
 361 Value::ListStorage Value::TakeList() {
 362   CHECK(is_list());
 363   return std::exchange(list_, ListStorage());
 364 }
 365
 366 void Value::Append(bool value) {
 367   CHECK(is_list());
 368   list_.emplace_back(value);
 369 }
 370
 371 void Value::Append(int value) {
 372   CHECK(is_list());
 373   list_.emplace_back(value);
 374 }
 375
 376 void Value::Append(double value) {
 377   CHECK(is_list());
 378   list_.emplace_back(value);
 379 }
 380
 381 void Value::Append(const char* value) {
 382   CHECK(is_list());
 383   list_.emplace_back(value);
 384 }
 385
 386 void Value::Append(StringPiece value) {
 387   CHECK(is_list());
 388   list_.emplace_back(value);
 389 }
 390
 391 void Value::Append(std::string&& value) {
 392   CHECK(is_list());
 393   list_.emplace_back(std::move(value));
 394 }
 395
 396 void Value::Append(const char16* value) {
 397   CHECK(is_list());
 398   list_.emplace_back(value);
 399 }
 400
 401 void Value::Append(StringPiece16 value) {
 402   CHECK(is_list());
 403   list_.emplace_back(value);
 404 }
 405
 406 void Value::Append(Value&& value) {
 407   CHECK(is_list());
 408   list_.emplace_back(std::move(value));
 409 }
 410
 411 CheckedContiguousIterator<Value> Value::Insert(
 412     CheckedContiguousConstIterator<Value> pos,
 413     Value&& value) {
 414   CHECK(is_list());
 415   const auto offset = pos - make_span(list_).begin();
 416   list_.insert(list_.begin() + offset, std::move(value));
 417   return make_span(list_).begin() + offset;
 418 }
 419
 420 bool Value::EraseListIter(CheckedContiguousConstIterator<Value> iter) {
 421   CHECK(is_list());
 422   const auto offset = iter - ListView(list_).begin();
 423   auto list_iter = list_.begin() + offset;
 424   if (list_iter == list_.end())
 425     return false;
 426
 427   list_.erase(list_iter);
 428   return true;
 429 }
 430
 431 size_t Value::EraseListValue(const Value& val) {
 432   return EraseListValueIf([&val](const Value& other) { return val == other; });
 433 }
 434
 435 void Value::ClearList() {
 436   CHECK(is_list());
 437   list_.clear();
 438 }
 439
 440 Value* Value::FindKey(StringPiece key) {
 441   return const_cast<Value*>(as_const(*this).FindKey(key));
 442 }
 443
 444 const Value* Value::FindKey(StringPiece key) const {
 445   CHECK(is_dict());
 446   auto found = dict_.find(key);
 447   if (found == dict_.end())
 448     return nullptr;
 449   return found->second.get();
 450 }
 451
 452 Value* Value::FindKeyOfType(StringPiece key, Type type) {
 453   return const_cast<Value*>(as_const(*this).FindKeyOfType(key, type));
 454 }
 455
 456 const Value* Value::FindKeyOfType(StringPiece key, Type type) const {
 457   const Value* result = FindKey(key);
 458   if (!result || result->type() != type)
 459     return nullptr;
 460   return result;
 461 }
 462
 463 base::Optional<bool> Value::FindBoolKey(StringPiece key) const {
 464   const Value* result = FindKeyOfType(key, Type::BOOLEAN);
 465   return result ? base::make_optional(result->bool_value_) : base::nullopt;
 466 }
 467
 468 base::Optional<int> Value::FindIntKey(StringPiece key) const {
 469   const Value* result = FindKeyOfType(key, Type::INTEGER);
 470   return result ? base::make_optional(result->int_value_) : base::nullopt;
 471 }
 472
 473 base::Optional<double> Value::FindDoubleKey(StringPiece key) const {
 474   const Value* result = FindKey(key);
 475   if (result) {
 476     if (result->is_int())
 477       return static_cast<double>(result->int_value_);
 478     if (result->is_double()) {
 479       return result->AsDoubleInternal();
 480     }
 481   }
 482   return base::nullopt;
 483 }
 484
 485 const std::string* Value::FindStringKey(StringPiece key) const {
 486   const Value* result = FindKeyOfType(key, Type::STRING);
 487   return result ? &result->string_value_ : nullptr;
 488 }
 489
 490 std::string* Value::FindStringKey(StringPiece key) {
 491   Value* result = FindKeyOfType(key, Type::STRING);
 492   return result ? &result->string_value_ : nullptr;
 493 }
 494
 495 const Value::BlobStorage* Value::FindBlobKey(StringPiece key) const {
 496   const Value* value = FindKeyOfType(key, Type::BINARY);
 497   return value ? &value->binary_value_ : nullptr;
 498 }
 499
 500 const Value* Value::FindDictKey(StringPiece key) const {
 501   return FindKeyOfType(key, Type::DICTIONARY);
 502 }
 503
 504 Value* Value::FindDictKey(StringPiece key) {
 505   return FindKeyOfType(key, Type::DICTIONARY);
 506 }
 507
 508 const Value* Value::FindListKey(StringPiece key) const {
 509   return FindKeyOfType(key, Type::LIST);
 510 }
 511
 512 Value* Value::FindListKey(StringPiece key) {
 513   return FindKeyOfType(key, Type::LIST);
 514 }
 515
 516 Value* Value::SetKey(StringPiece key, Value&& value) {
 517   return SetKeyInternal(key, std::make_unique<Value>(std::move(value)));
 518 }
 519
 520 Value* Value::SetKey(std::string&& key, Value&& value) {
 521   CHECK(is_dict());
 522   return dict_
 523       .insert_or_assign(std::move(key),
 524                         std::make_unique<Value>(std::move(value)))
 525       .first->second.get();
 526 }
 527
 528 Value* Value::SetKey(const char* key, Value&& value) {
 529   return SetKeyInternal(key, std::make_unique<Value>(std::move(value)));
 530 }
 531
 532 Value* Value::SetBoolKey(StringPiece key, bool value) {
 533   return SetKeyInternal(key, std::make_unique<Value>(value));
 534 }
 535
 536 Value* Value::SetIntKey(StringPiece key, int value) {
 537   return SetKeyInternal(key, std::make_unique<Value>(value));
 538 }
 539
 540 Value* Value::SetDoubleKey(StringPiece key, double value) {
 541   return SetKeyInternal(key, std::make_unique<Value>(value));
 542 }
 543
 544 Value* Value::SetStringKey(StringPiece key, StringPiece value) {
 545   return SetKeyInternal(key, std::make_unique<Value>(value));
 546 }
 547
 548 Value* Value::SetStringKey(StringPiece key, StringPiece16 value) {
 549   return SetKeyInternal(key, std::make_unique<Value>(value));
 550 }
 551
 552 Value* Value::SetStringKey(StringPiece key, const char* value) {
 553   return SetKeyInternal(key, std::make_unique<Value>(value));
 554 }
 555
 556 Value* Value::SetStringKey(StringPiece key, std::string&& value) {
 557   return SetKeyInternal(key, std::make_unique<Value>(std::move(value)));
 558 }
 559
 560 bool Value::RemoveKey(StringPiece key) {
 561   CHECK(is_dict());
 562   return dict_.erase(key) != 0;
 563 }
 564
 565 Optional<Value> Value::ExtractKey(StringPiece key) {
 566   CHECK(is_dict());
 567   auto found = dict_.find(key);
 568   if (found == dict_.end())
 569     return nullopt;
 570
 571   Value value = std::move(*found->second);
 572   dict_.erase(found);
 573   return std::move(value);
 574 }
 575
 576 Value* Value::FindPath(StringPiece path) {
 577   return const_cast<Value*>(as_const(*this).FindPath(path));
 578 }
 579
 580 const Value* Value::FindPath(StringPiece path) const {
 581   CHECK(is_dict());
 582   const Value* cur = this;
 583   PathSplitter splitter(path);
 584   while (splitter.HasNext()) {
 585     if (!cur->is_dict() || (cur = cur->FindKey(splitter.Next())) == nullptr)
 586       return nullptr;
 587   }
 588   return cur;
 589 }
 590
 591 Value* Value::FindPathOfType(StringPiece path, Type type) {
 592   return const_cast<Value*>(as_const(*this).FindPathOfType(path, type));
 593 }
 594
 595 const Value* Value::FindPathOfType(StringPiece path, Type type) const {
 596   const Value* cur = FindPath(path);
 597   if (!cur || cur->type() != type)
 598     return nullptr;
 599   return cur;
 600 }
 601
 602 base::Optional<bool> Value::FindBoolPath(StringPiece path) const {
 603   const Value* cur = FindPath(path);
 604   if (!cur || !cur->is_bool())
 605     return base::nullopt;
 606   return cur->bool_value_;
 607 }
 608
 609 base::Optional<int> Value::FindIntPath(StringPiece path) const {
 610   const Value* cur = FindPath(path);
 611   if (!cur || !cur->is_int())
 612     return base::nullopt;
 613   return cur->int_value_;
 614 }
 615
 616 base::Optional<double> Value::FindDoublePath(StringPiece path) const {
 617   const Value* cur = FindPath(path);
 618   if (cur) {
 619     if (cur->is_int())
 620       return static_cast<double>(cur->int_value_);
 621     if (cur->is_double())
 622       return cur->AsDoubleInternal();
 623   }
 624   return base::nullopt;
 625 }
 626
 627 const std::string* Value::FindStringPath(StringPiece path) const {
 628   const Value* cur = FindPath(path);
 629   if (!cur || !cur->is_string())
 630     return nullptr;
 631   return &cur->string_value_;
 632 }
 633
 634 std::string* Value::FindStringPath(StringPiece path) {
 635   return const_cast<std::string*>(as_const(*this).FindStringPath(path));
 636 }
 637
 638 const Value::BlobStorage* Value::FindBlobPath(StringPiece path) const {
 639   const Value* cur = FindPath(path);
 640   if (!cur || !cur->is_blob())
 641     return nullptr;
 642   return &cur->binary_value_;
 643 }
 644
 645 const Value* Value::FindDictPath(StringPiece path) const {
 646   return FindPathOfType(path, Type::DICTIONARY);
 647 }
 648
 649 Value* Value::FindDictPath(StringPiece path) {
 650   return FindPathOfType(path, Type::DICTIONARY);
 651 }
 652
 653 const Value* Value::FindListPath(StringPiece path) const {
 654   return FindPathOfType(path, Type::LIST);
 655 }
 656
 657 Value* Value::FindListPath(StringPiece path) {
 658   return FindPathOfType(path, Type::LIST);
 659 }
 660
 661 Value* Value::SetPath(StringPiece path, Value&& value) {
 662   return SetPathInternal(path, std::make_unique<Value>(std::move(value)));
 663 }
 664
 665 Value* Value::SetBoolPath(StringPiece path, bool value) {
 666   return SetPathInternal(path, std::make_unique<Value>(value));
 667 }
 668
 669 Value* Value::SetIntPath(StringPiece path, int value) {
 670   return SetPathInternal(path, std::make_unique<Value>(value));
 671 }
 672
 673 Value* Value::SetDoublePath(StringPiece path, double value) {
 674   return SetPathInternal(path, std::make_unique<Value>(value));
 675 }
 676
 677 Value* Value::SetStringPath(StringPiece path, StringPiece value) {
 678   return SetPathInternal(path, std::make_unique<Value>(value));
 679 }
 680
 681 Value* Value::SetStringPath(StringPiece path, std::string&& value) {
 682   return SetPathInternal(path, std::make_unique<Value>(std::move(value)));
 683 }
 684
 685 Value* Value::SetStringPath(StringPiece path, const char* value) {
 686   return SetPathInternal(path, std::make_unique<Value>(value));
 687 }
 688
 689 Value* Value::SetStringPath(StringPiece path, StringPiece16 value) {
 690   return SetPathInternal(path, std::make_unique<Value>(value));
 691 }
 692
 693 bool Value::RemovePath(StringPiece path) {
 694   return ExtractPath(path).has_value();
 695 }
 696
 697 Optional<Value> Value::ExtractPath(StringPiece path) {
 698   if (!is_dict() || path.empty())
 699     return nullopt;
 700
 701   // NOTE: PathSplitter is not being used here because recursion is used to
 702   // ensure that dictionaries that become empty due to this operation are
 703   // removed automatically.
 704   size_t pos = path.find('.');
 705   if (pos == path.npos)
 706     return ExtractKey(path);
 707
 708   auto found = dict_.find(path.substr(0, pos));
 709   if (found == dict_.end() || !found->second->is_dict())
 710     return nullopt;
 711
 712   Optional<Value> extracted = found->second->ExtractPath(path.substr(pos + 1));
 713   if (extracted && found->second->dict_.empty())
 714     dict_.erase(found);
 715
 716   return extracted;
 717 }
 718
 719 // DEPRECATED METHODS
 720 Value* Value::FindPath(std::initializer_list<StringPiece> path) {
 721   return const_cast<Value*>(as_const(*this).FindPath(path));
 722 }
 723
 724 Value* Value::FindPath(span<const StringPiece> path) {
 725   return const_cast<Value*>(as_const(*this).FindPath(path));
 726 }
 727
 728 const Value* Value::FindPath(std::initializer_list<StringPiece> path) const {
 729   DCHECK_GE(path.size(), 2u) << "Use FindKey() for a path of length 1.";
 730   return FindPath(make_span(path.begin(), path.size()));
 731 }
 732
 733 const Value* Value::FindPath(span<const StringPiece> path) const {
 734   const Value* cur = this;
 735   for (const StringPiece component : path) {
 736     if (!cur->is_dict() || (cur = cur->FindKey(component)) == nullptr)
 737       return nullptr;
 738   }
 739   return cur;
 740 }
 741
 742 Value* Value::FindPathOfType(std::initializer_list<StringPiece> path,
 743                              Type type) {
 744   return const_cast<Value*>(as_const(*this).FindPathOfType(path, type));
 745 }
 746
 747 Value* Value::FindPathOfType(span<const StringPiece> path, Type type) {
 748   return const_cast<Value*>(as_const(*this).FindPathOfType(path, type));
 749 }
 750
 751 const Value* Value::FindPathOfType(std::initializer_list<StringPiece> path,
 752                                    Type type) const {
 753   DCHECK_GE(path.size(), 2u) << "Use FindKeyOfType() for a path of length 1.";
 754   return FindPathOfType(make_span(path.begin(), path.size()), type);
 755 }
 756
 757 const Value* Value::FindPathOfType(span<const StringPiece> path,
 758                                    Type type) const {
 759   const Value* result = FindPath(path);
 760   if (!result || result->type() != type)
 761     return nullptr;
 762   return result;
 763 }
 764
 765 Value* Value::SetPath(std::initializer_list<StringPiece> path, Value&& value) {
 766   DCHECK_GE(path.size(), 2u) << "Use SetKey() for a path of length 1.";
 767   return SetPath(make_span(path.begin(), path.size()), std::move(value));
 768 }
 769
 770 Value* Value::SetPath(span<const StringPiece> path, Value&& value) {
 771   DCHECK(path.begin() != path.end());  // Can't be empty path.
 772
 773   // Walk/construct intermediate dictionaries. The last element requires
 774   // special handling so skip it in this loop.
 775   Value* cur = this;
 776   auto cur_path = path.begin();
 777   for (; (cur_path + 1) < path.end(); ++cur_path) {
 778     if (!cur->is_dict())
 779       return nullptr;
 780
 781     // Use lower_bound to avoid doing the search twice for missing keys.
 782     const StringPiece path_component = *cur_path;
 783     auto found = cur->dict_.lower_bound(path_component);
 784     if (found == cur->dict_.end() || found->first != path_component) {
 785       // No key found, insert one.
 786       auto inserted = cur->dict_.try_emplace(
 787           found, path_component, std::make_unique<Value>(Type::DICTIONARY));
 788       cur = inserted->second.get();
 789     } else {
 790       cur = found->second.get();
 791     }
 792   }
 793
 794   // "cur" will now contain the last dictionary to insert or replace into.
 795   if (!cur->is_dict())
 796     return nullptr;
 797   return cur->SetKey(*cur_path, std::move(value));
 798 }
 799
 800 bool Value::RemovePath(std::initializer_list<StringPiece> path) {
 801   DCHECK_GE(path.size(), 2u) << "Use RemoveKey() for a path of length 1.";
 802   return RemovePath(make_span(path.begin(), path.size()));
 803 }
 804
 805 bool Value::RemovePath(span<const StringPiece> path) {
 806   if (!is_dict() || path.empty())
 807     return false;
 808
 809   if (path.size() == 1)
 810     return RemoveKey(path[0]);
 811
 812   auto found = dict_.find(path[0]);
 813   if (found == dict_.end() || !found->second->is_dict())
 814     return false;
 815
 816   bool removed = found->second->RemovePath(path.subspan(1));
 817   if (removed && found->second->dict_.empty())
 818     dict_.erase(found);
 819
 820   return removed;
 821 }
 822
 823 Value::dict_iterator_proxy Value::DictItems() {
 824   CHECK(is_dict());
 825   return dict_iterator_proxy(&dict_);
 826 }
 827
 828 Value::const_dict_iterator_proxy Value::DictItems() const {
 829   CHECK(is_dict());
 830   return const_dict_iterator_proxy(&dict_);
 831 }
 832
 833 size_t Value::DictSize() const {
 834   CHECK(is_dict());
 835   return dict_.size();
 836 }
 837
 838 bool Value::DictEmpty() const {
 839   CHECK(is_dict());
 840   return dict_.empty();
 841 }
 842
 843 void Value::MergeDictionary(const Value* dictionary) {
 844   CHECK(is_dict());
 845   CHECK(dictionary->is_dict());
 846   for (const auto& pair : dictionary->dict_) {
 847     const auto& key = pair.first;
 848     const auto& val = pair.second;
 849     // Check whether we have to merge dictionaries.
 850     if (val->is_dict()) {
 851       auto found = dict_.find(key);
 852       if (found != dict_.end() && found->second->is_dict()) {
 853         found->second->MergeDictionary(val.get());
 854         continue;
 855       }
 856     }
 857
 858     // All other cases: Make a copy and hook it up.
 859     SetKey(key, val->Clone());
 860   }
 861 }
 862
 863 bool Value::GetAsBoolean(bool* out_value) const {
 864   if (out_value && is_bool()) {
 865     *out_value = bool_value_;
 866     return true;
 867   }
 868   return is_bool();
 869 }
 870
 871 bool Value::GetAsInteger(int* out_value) const {
 872   if (out_value && is_int()) {
 873     *out_value = int_value_;
 874     return true;
 875   }
 876   return is_int();
 877 }
 878
 879 bool Value::GetAsDouble(double* out_value) const {
 880   if (out_value && is_double()) {
 881     *out_value = AsDoubleInternal();
 882     return true;
 883   }
 884   if (out_value && is_int()) {
 885     // Allow promotion from int to double.
 886     *out_value = int_value_;
 887     return true;
 888   }
 889   return is_double() || is_int();
 890 }
 891
 892 bool Value::GetAsString(std::string* out_value) const {
 893   if (out_value && is_string()) {
 894     *out_value = string_value_;
 895     return true;
 896   }
 897   return is_string();
 898 }
 899
 900 bool Value::GetAsString(string16* out_value) const {
 901   if (out_value && is_string()) {
 902     *out_value = UTF8ToUTF16(string_value_);
 903     return true;
 904   }
 905   return is_string();
 906 }
 907
 908 bool Value::GetAsString(const Value** out_value) const {
 909   if (out_value && is_string()) {
 910     *out_value = this;
 911     return true;
 912   }
 913   return is_string();
 914 }
 915
 916 bool Value::GetAsString(StringPiece* out_value) const {
 917   if (out_value && is_string()) {
 918     *out_value = string_value_;
 919     return true;
 920   }
 921   return is_string();
 922 }
 923
 924 bool Value::GetAsList(ListValue** out_value) {
 925   if (out_value && is_list()) {
 926     *out_value = static_cast<ListValue*>(this);
 927     return true;
 928   }
 929   return is_list();
 930 }
 931
 932 bool Value::GetAsList(const ListValue** out_value) const {
 933   if (out_value && is_list()) {
 934     *out_value = static_cast<const ListValue*>(this);
 935     return true;
 936   }
 937   return is_list();
 938 }
 939
 940 bool Value::GetAsDictionary(DictionaryValue** out_value) {
 941   if (out_value && is_dict()) {
 942     *out_value = static_cast<DictionaryValue*>(this);
 943     return true;
 944   }
 945   return is_dict();
 946 }
 947
 948 bool Value::GetAsDictionary(const DictionaryValue** out_value) const {
 949   if (out_value && is_dict()) {
 950     *out_value = static_cast<const DictionaryValue*>(this);
 951     return true;
 952   }
 953   return is_dict();
 954 }
 955
 956 Value* Value::DeepCopy() const {
 957   return new Value(Clone());
 958 }
 959
 960 std::unique_ptr<Value> Value::CreateDeepCopy() const {
 961   return std::make_unique<Value>(Clone());
 962 }
 963
 964 bool operator==(const Value& lhs, const Value& rhs) {
 965   if (lhs.type_ != rhs.type_)
 966     return false;
 967
 968   switch (lhs.type_) {
 969     case Value::Type::NONE:
 970       return true;
 971     case Value::Type::BOOLEAN:
 972       return lhs.bool_value_ == rhs.bool_value_;
 973     case Value::Type::INTEGER:
 974       return lhs.int_value_ == rhs.int_value_;
 975     case Value::Type::DOUBLE:
 976       return lhs.AsDoubleInternal() == rhs.AsDoubleInternal();
 977     case Value::Type::STRING:
 978       return lhs.string_value_ == rhs.string_value_;
 979     case Value::Type::BINARY:
 980       return lhs.binary_value_ == rhs.binary_value_;
 981     // TODO(crbug.com/646113): Clean this up when DictionaryValue and ListValue
 982     // are completely inlined.
 983     case Value::Type::DICTIONARY:
 984       if (lhs.dict_.size() != rhs.dict_.size())
 985         return false;
 986       return std::equal(std::begin(lhs.dict_), std::end(lhs.dict_),
 987                         std::begin(rhs.dict_),
 988                         [](const auto& u, const auto& v) {
 989                           return std::tie(u.first, *u.second) ==
 990                                  std::tie(v.first, *v.second);
 991                         });
 992     case Value::Type::LIST:
 993       return lhs.list_ == rhs.list_;
 994       // TODO(crbug.com/859477): Remove after root cause is found.
 995     case Value::Type::DEAD:
 996       CHECK(false);
 997       return false;
 998   }
 999
1000   // TODO(crbug.com/859477): Revert to NOTREACHED() after root cause is found.
1001   CHECK(false);
1002   return false;
1003 }
1004
1005 bool operator!=(const Value& lhs, const Value& rhs) {
1006   return !(lhs == rhs);
1007 }
1008
1009 bool operator<(const Value& lhs, const Value& rhs) {
1010   if (lhs.type_ != rhs.type_)
1011     return lhs.type_ < rhs.type_;
1012
1013   switch (lhs.type_) {
1014     case Value::Type::NONE:
1015       return false;
1016     case Value::Type::BOOLEAN:
1017       return lhs.bool_value_ < rhs.bool_value_;
1018     case Value::Type::INTEGER:
1019       return lhs.int_value_ < rhs.int_value_;
1020     case Value::Type::DOUBLE:
1021       return lhs.AsDoubleInternal() < rhs.AsDoubleInternal();
1022     case Value::Type::STRING:
1023       return lhs.string_value_ < rhs.string_value_;
1024     case Value::Type::BINARY:
1025       return lhs.binary_value_ < rhs.binary_value_;
1026     // TODO(crbug.com/646113): Clean this up when DictionaryValue and ListValue
1027     // are completely inlined.
1028     case Value::Type::DICTIONARY:
1029       return std::lexicographical_compare(
1030           std::begin(lhs.dict_), std::end(lhs.dict_), std::begin(rhs.dict_),
1031           std::end(rhs.dict_),
1032           [](const Value::DictStorage::value_type& u,
1033              const Value::DictStorage::value_type& v) {
1034             return std::tie(u.first, *u.second) < std::tie(v.first, *v.second);
1035           });
1036     case Value::Type::LIST:
1037       return lhs.list_ < rhs.list_;
1038       // TODO(crbug.com/859477): Remove after root cause is found.
1039     case Value::Type::DEAD:
1040       CHECK(false);
1041       return false;
1042   }
1043
1044   // TODO(crbug.com/859477): Revert to NOTREACHED() after root cause is found.
1045   CHECK(false);
1046   return false;
1047 }
1048
1049 bool operator>(const Value& lhs, const Value& rhs) {
1050   return rhs < lhs;
1051 }
1052
1053 bool operator<=(const Value& lhs, const Value& rhs) {
1054   return !(rhs < lhs);
1055 }
1056
1057 bool operator>=(const Value& lhs, const Value& rhs) {
1058   return !(lhs < rhs);
1059 }
1060
1061 bool Value::Equals(const Value* other) const {
1062   DCHECK(other);
1063   return *this == *other;
1064 }
1065
1066 size_t Value::EstimateMemoryUsage() const {
1067   switch (type_) {
1068 #if BUILDFLAG(ENABLE_BASE_TRACING)
1069     case Type::STRING:
1070       return base::trace_event::EstimateMemoryUsage(string_value_);
1071     case Type::BINARY:
1072       return base::trace_event::EstimateMemoryUsage(binary_value_);
1073     case Type::DICTIONARY:
1074       return base::trace_event::EstimateMemoryUsage(dict_);
1075     case Type::LIST:
1076       return base::trace_event::EstimateMemoryUsage(list_);
1077 #endif  // BUILDFLAG(ENABLE_BASE_TRACING)
1078     default:
1079       return 0;
1080   }
1081 }
1082
1083 void Value::InternalMoveConstructFrom(Value&& that) {
1084   type_ = that.type_;
1085
1086   switch (type_) {
1087     case Type::NONE:
1088       return;
1089     case Type::BOOLEAN:
1090       bool_value_ = that.bool_value_;
1091       return;
1092     case Type::INTEGER:
1093       int_value_ = that.int_value_;
1094       return;
1095     case Type::DOUBLE:
1096       double_value_ = that.double_value_;
1097       return;
1098     case Type::STRING:
1099       new (&string_value_) std::string(std::move(that.string_value_));
1100       return;
1101     case Type::BINARY:
1102       new (&binary_value_) BlobStorage(std::move(that.binary_value_));
1103       return;
1104     case Type::DICTIONARY:
1105       new (&dict_) DictStorage(std::move(that.dict_));
1106       return;
1107     case Type::LIST:
1108       new (&list_) ListStorage(std::move(that.list_));
1109       return;
1110       // TODO(crbug.com/859477): Remove after root cause is found.
1111     case Type::DEAD:
1112       CHECK(false);
1113       return;
1114   }
1115
1116   // TODO(crbug.com/859477): Revert to NOTREACHED() after root cause is found.
1117   CHECK(false);
1118 }
1119
1120 void Value::InternalCleanup() {
1121   switch (type_) {
1122     case Type::NONE:
1123     case Type::BOOLEAN:
1124     case Type::INTEGER:
1125     case Type::DOUBLE:
1126       // Nothing to do
1127       return;
1128
1129     case Type::STRING:
1130       string_value_.~basic_string();
1131       return;
1132     case Type::BINARY:
1133       binary_value_.~BlobStorage();
1134       return;
1135     case Type::DICTIONARY:
1136       dict_.~DictStorage();
1137       return;
1138     case Type::LIST:
1139       list_.~ListStorage();
1140       return;
1141       // TODO(crbug.com/859477): Remove after root cause is found.
1142     case Type::DEAD:
1143       CHECK(false);
1144       return;
1145   }
1146
1147   // TODO(crbug.com/859477): Revert to NOTREACHED() after root cause is found.
1148   CHECK(false);
1149 }
1150
1151 Value* Value::SetKeyInternal(StringPiece key,
1152                              std::unique_ptr<Value>&& val_ptr) {
1153   CHECK(is_dict());
1154   // NOTE: We can't use |insert_or_assign| here, as only |try_emplace| does
1155   // an explicit conversion from StringPiece to std::string if necessary.
1156   auto result = dict_.try_emplace(key, std::move(val_ptr));
1157   if (!result.second) {
1158     // val_ptr is guaranteed to be still intact at this point.
1159     result.first->second = std::move(val_ptr);
1160   }
1161   return result.first->second.get();
1162 }
1163
1164 Value* Value::SetPathInternal(StringPiece path,
1165                               std::unique_ptr<Value>&& value_ptr) {
1166   PathSplitter splitter(path);
1167   DCHECK(splitter.HasNext()) << "Cannot call SetPath() with empty path";
1168   // Walk/construct intermediate dictionaries. The last element requires
1169   // special handling so skip it in this loop.
1170   Value* cur = this;
1171   StringPiece path_component = splitter.Next();
1172   while (splitter.HasNext()) {
1173     if (!cur->is_dict())
1174       return nullptr;
1175
1176     // Use lower_bound to avoid doing the search twice for missing keys.
1177     auto found = cur->dict_.lower_bound(path_component);
1178     if (found == cur->dict_.end() || found->first != path_component) {
1179       // No key found, insert one.
1180       auto inserted = cur->dict_.try_emplace(
1181           found, path_component, std::make_unique<Value>(Type::DICTIONARY));
1182       cur = inserted->second.get();
1183     } else {
1184       cur = found->second.get();
1185     }
1186     path_component = splitter.Next();
1187   }
1188
1189   // "cur" will now contain the last dictionary to insert or replace into.
1190   if (!cur->is_dict())
1191     return nullptr;
1192   return cur->SetKeyInternal(path_component, std::move(value_ptr));
1193 }
1194
1195 ///////////////////// DictionaryValue ////////////////////
1196
1197 // static
1198 std::unique_ptr<DictionaryValue> DictionaryValue::From(
1199     std::unique_ptr<Value> value) {
1200   DictionaryValue* out;
1201   if (value && value->GetAsDictionary(&out)) {
1202     ignore_result(value.release());
1203     return WrapUnique(out);
1204   }
1205   return nullptr;
1206 }
1207
1208 DictionaryValue::DictionaryValue() : Value(Type::DICTIONARY) {}
1209 DictionaryValue::DictionaryValue(const DictStorage& in_dict) : Value(in_dict) {}
1210 DictionaryValue::DictionaryValue(DictStorage&& in_dict) noexcept
1211     : Value(std::move(in_dict)) {}
1212
1213 bool DictionaryValue::HasKey(StringPiece key) const {
1214   DCHECK(IsStringUTF8AllowingNoncharacters(key));
1215   auto current_entry = dict_.find(key);
1216   DCHECK((current_entry == dict_.end()) || current_entry->second);
1217   return current_entry != dict_.end();
1218 }
1219
1220 void DictionaryValue::Clear() {
1221   dict_.clear();
1222 }
1223
1224 Value* DictionaryValue::Set(StringPiece path, std::unique_ptr<Value> in_value) {
1225   DCHECK(IsStringUTF8AllowingNoncharacters(path));
1226   DCHECK(in_value);
1227
1228   // IMPORTANT NOTE: Do not replace with SetPathInternal() yet, because the
1229   // latter fails when over-writing a non-dict intermediate node, while this
1230   // method just replaces it with one. This difference makes some tests actually
1231   // fail (http://crbug.com/949461).
1232   StringPiece current_path(path);
1233   Value* current_dictionary = this;
1234   for (size_t delimiter_position = current_path.find('.');
1235        delimiter_position != StringPiece::npos;
1236        delimiter_position = current_path.find('.')) {
1237     // Assume that we're indexing into a dictionary.
1238     StringPiece key = current_path.substr(0, delimiter_position);
1239     Value* child_dictionary =
1240         current_dictionary->FindKeyOfType(key, Type::DICTIONARY);
1241     if (!child_dictionary) {
1242       child_dictionary =
1243           current_dictionary->SetKey(key, Value(Type::DICTIONARY));
1244     }
1245
1246     current_dictionary = child_dictionary;
1247     current_path = current_path.substr(delimiter_position + 1);
1248   }
1249
1250   return static_cast<DictionaryValue*>(current_dictionary)
1251       ->SetWithoutPathExpansion(current_path, std::move(in_value));
1252 }
1253
1254 Value* DictionaryValue::SetBoolean(StringPiece path, bool in_value) {
1255   return Set(path, std::make_unique<Value>(in_value));
1256 }
1257
1258 Value* DictionaryValue::SetInteger(StringPiece path, int in_value) {
1259   return Set(path, std::make_unique<Value>(in_value));
1260 }
1261
1262 Value* DictionaryValue::SetDouble(StringPiece path, double in_value) {
1263   return Set(path, std::make_unique<Value>(in_value));
1264 }
1265
1266 Value* DictionaryValue::SetString(StringPiece path, StringPiece in_value) {
1267   return Set(path, std::make_unique<Value>(in_value));
1268 }
1269
1270 Value* DictionaryValue::SetString(StringPiece path, const string16& in_value) {
1271   return Set(path, std::make_unique<Value>(in_value));
1272 }
1273
1274 DictionaryValue* DictionaryValue::SetDictionary(
1275     StringPiece path,
1276     std::unique_ptr<DictionaryValue> in_value) {
1277   return static_cast<DictionaryValue*>(Set(path, std::move(in_value)));
1278 }
1279
1280 ListValue* DictionaryValue::SetList(StringPiece path,
1281                                     std::unique_ptr<ListValue> in_value) {
1282   return static_cast<ListValue*>(Set(path, std::move(in_value)));
1283 }
1284
1285 Value* DictionaryValue::SetWithoutPathExpansion(
1286     StringPiece key,
1287     std::unique_ptr<Value> in_value) {
1288   // NOTE: We can't use |insert_or_assign| here, as only |try_emplace| does
1289   // an explicit conversion from StringPiece to std::string if necessary.
1290   auto result = dict_.try_emplace(key, std::move(in_value));
1291   if (!result.second) {
1292     // in_value is guaranteed to be still intact at this point.
1293     result.first->second = std::move(in_value);
1294   }
1295   return result.first->second.get();
1296 }
1297
1298 bool DictionaryValue::Get(StringPiece path,
1299                           const Value** out_value) const {
1300   DCHECK(IsStringUTF8AllowingNoncharacters(path));
1301   const Value* value = FindPath(path);
1302   if (!value)
1303     return false;
1304   if (out_value)
1305     *out_value = value;
1306   return true;
1307 }
1308
1309 bool DictionaryValue::Get(StringPiece path, Value** out_value)  {
1310   return as_const(*this).Get(path, const_cast<const Value**>(out_value));
1311 }
1312
1313 bool DictionaryValue::GetBoolean(StringPiece path, bool* bool_value) const {
1314   const Value* value;
1315   if (!Get(path, &value))
1316     return false;
1317
1318   return value->GetAsBoolean(bool_value);
1319 }
1320
1321 bool DictionaryValue::GetInteger(StringPiece path, int* out_value) const {
1322   const Value* value;
1323   if (!Get(path, &value))
1324     return false;
1325
1326   return value->GetAsInteger(out_value);
1327 }
1328
1329 bool DictionaryValue::GetDouble(StringPiece path, double* out_value) const {
1330   const Value* value;
1331   if (!Get(path, &value))
1332     return false;
1333
1334   return value->GetAsDouble(out_value);
1335 }
1336
1337 bool DictionaryValue::GetString(StringPiece path,
1338                                 std::string* out_value) const {
1339   const Value* value;
1340   if (!Get(path, &value))
1341     return false;
1342
1343   return value->GetAsString(out_value);
1344 }
1345
1346 bool DictionaryValue::GetString(StringPiece path, string16* out_value) const {
1347   const Value* value;
1348   if (!Get(path, &value))
1349     return false;
1350
1351   return value->GetAsString(out_value);
1352 }
1353
1354 bool DictionaryValue::GetStringASCII(StringPiece path,
1355                                      std::string* out_value) const {
1356   std::string out;
1357   if (!GetString(path, &out))
1358     return false;
1359
1360   if (!IsStringASCII(out)) {
1361     NOTREACHED();
1362     return false;
1363   }
1364
1365   out_value->assign(out);
1366   return true;
1367 }
1368
1369 bool DictionaryValue::GetBinary(StringPiece path,
1370                                 const Value** out_value) const {
1371   const Value* value;
1372   bool result = Get(path, &value);
1373   if (!result || !value->is_blob())
1374     return false;
1375
1376   if (out_value)
1377     *out_value = value;
1378
1379   return true;
1380 }
1381
1382 bool DictionaryValue::GetBinary(StringPiece path, Value** out_value) {
1383   return as_const(*this).GetBinary(path, const_cast<const Value**>(out_value));
1384 }
1385
1386 bool DictionaryValue::GetDictionary(StringPiece path,
1387                                     const DictionaryValue** out_value) const {
1388   const Value* value;
1389   bool result = Get(path, &value);
1390   if (!result || !value->is_dict())
1391     return false;
1392
1393   if (out_value)
1394     *out_value = static_cast<const DictionaryValue*>(value);
1395
1396   return true;
1397 }
1398
1399 bool DictionaryValue::GetDictionary(StringPiece path,
1400                                     DictionaryValue** out_value) {
1401   return as_const(*this).GetDictionary(
1402       path, const_cast<const DictionaryValue**>(out_value));
1403 }
1404
1405 bool DictionaryValue::GetList(StringPiece path,
1406                               const ListValue** out_value) const {
1407   const Value* value;
1408   bool result = Get(path, &value);
1409   if (!result || !value->is_list())
1410     return false;
1411
1412   if (out_value)
1413     *out_value = static_cast<const ListValue*>(value);
1414
1415   return true;
1416 }
1417
1418 bool DictionaryValue::GetList(StringPiece path, ListValue** out_value) {
1419   return as_const(*this).GetList(path,
1420                                  const_cast<const ListValue**>(out_value));
1421 }
1422
1423 bool DictionaryValue::GetWithoutPathExpansion(StringPiece key,
1424                                               const Value** out_value) const {
1425   DCHECK(IsStringUTF8AllowingNoncharacters(key));
1426   auto entry_iterator = dict_.find(key);
1427   if (entry_iterator == dict_.end())
1428     return false;
1429
1430   if (out_value)
1431     *out_value = entry_iterator->second.get();
1432   return true;
1433 }
1434
1435 bool DictionaryValue::GetWithoutPathExpansion(StringPiece key,
1436                                               Value** out_value) {
1437   return as_const(*this).GetWithoutPathExpansion(
1438       key, const_cast<const Value**>(out_value));
1439 }
1440
1441 bool DictionaryValue::GetBooleanWithoutPathExpansion(StringPiece key,
1442                                                      bool* out_value) const {
1443   const Value* value;
1444   if (!GetWithoutPathExpansion(key, &value))
1445     return false;
1446
1447   return value->GetAsBoolean(out_value);
1448 }
1449
1450 bool DictionaryValue::GetIntegerWithoutPathExpansion(StringPiece key,
1451                                                      int* out_value) const {
1452   const Value* value;
1453   if (!GetWithoutPathExpansion(key, &value))
1454     return false;
1455
1456   return value->GetAsInteger(out_value);
1457 }
1458
1459 bool DictionaryValue::GetDoubleWithoutPathExpansion(StringPiece key,
1460                                                     double* out_value) const {
1461   const Value* value;
1462   if (!GetWithoutPathExpansion(key, &value))
1463     return false;
1464
1465   return value->GetAsDouble(out_value);
1466 }
1467
1468 bool DictionaryValue::GetStringWithoutPathExpansion(
1469     StringPiece key,
1470     std::string* out_value) const {
1471   const Value* value;
1472   if (!GetWithoutPathExpansion(key, &value))
1473     return false;
1474
1475   return value->GetAsString(out_value);
1476 }
1477
1478 bool DictionaryValue::GetStringWithoutPathExpansion(StringPiece key,
1479                                                     string16* out_value) const {
1480   const Value* value;
1481   if (!GetWithoutPathExpansion(key, &value))
1482     return false;
1483
1484   return value->GetAsString(out_value);
1485 }
1486
1487 bool DictionaryValue::GetDictionaryWithoutPathExpansion(
1488     StringPiece key,
1489     const DictionaryValue** out_value) const {
1490   const Value* value;
1491   bool result = GetWithoutPathExpansion(key, &value);
1492   if (!result || !value->is_dict())
1493     return false;
1494
1495   if (out_value)
1496     *out_value = static_cast<const DictionaryValue*>(value);
1497
1498   return true;
1499 }
1500
1501 bool DictionaryValue::GetDictionaryWithoutPathExpansion(
1502     StringPiece key,
1503     DictionaryValue** out_value) {
1504   return as_const(*this).GetDictionaryWithoutPathExpansion(
1505       key, const_cast<const DictionaryValue**>(out_value));
1506 }
1507
1508 bool DictionaryValue::GetListWithoutPathExpansion(
1509     StringPiece key,
1510     const ListValue** out_value) const {
1511   const Value* value;
1512   bool result = GetWithoutPathExpansion(key, &value);
1513   if (!result || !value->is_list())
1514     return false;
1515
1516   if (out_value)
1517     *out_value = static_cast<const ListValue*>(value);
1518
1519   return true;
1520 }
1521
1522 bool DictionaryValue::GetListWithoutPathExpansion(StringPiece key,
1523                                                   ListValue** out_value) {
1524   return as_const(*this).GetListWithoutPathExpansion(
1525       key, const_cast<const ListValue**>(out_value));
1526 }
1527
1528 bool DictionaryValue::Remove(StringPiece path,
1529                              std::unique_ptr<Value>* out_value) {
1530   DCHECK(IsStringUTF8AllowingNoncharacters(path));
1531   StringPiece current_path(path);
1532   DictionaryValue* current_dictionary = this;
1533   size_t delimiter_position = current_path.rfind('.');
1534   if (delimiter_position != StringPiece::npos) {
1535     if (!GetDictionary(current_path.substr(0, delimiter_position),
1536                        &current_dictionary))
1537       return false;
1538     current_path = current_path.substr(delimiter_position + 1);
1539   }
1540
1541   return current_dictionary->RemoveWithoutPathExpansion(current_path,
1542                                                         out_value);
1543 }
1544
1545 bool DictionaryValue::RemoveWithoutPathExpansion(
1546     StringPiece key,
1547     std::unique_ptr<Value>* out_value) {
1548   DCHECK(IsStringUTF8AllowingNoncharacters(key));
1549   auto entry_iterator = dict_.find(key);
1550   if (entry_iterator == dict_.end())
1551     return false;
1552
1553   if (out_value)
1554     *out_value = std::move(entry_iterator->second);
1555   dict_.erase(entry_iterator);
1556   return true;
1557 }
1558
1559 bool DictionaryValue::RemovePath(StringPiece path,
1560                                  std::unique_ptr<Value>* out_value) {
1561   bool result = false;
1562   size_t delimiter_position = path.find('.');
1563
1564   if (delimiter_position == std::string::npos)
1565     return RemoveWithoutPathExpansion(path, out_value);
1566
1567   StringPiece subdict_path = path.substr(0, delimiter_position);
1568   DictionaryValue* subdict = nullptr;
1569   if (!GetDictionary(subdict_path, &subdict))
1570     return false;
1571   result = subdict->RemovePath(path.substr(delimiter_position + 1),
1572                                out_value);
1573   if (result && subdict->empty())
1574     RemoveWithoutPathExpansion(subdict_path, nullptr);
1575
1576   return result;
1577 }
1578
1579 std::unique_ptr<DictionaryValue> DictionaryValue::DeepCopyWithoutEmptyChildren()
1580     const {
1581   std::unique_ptr<DictionaryValue> copy =
1582       CopyDictionaryWithoutEmptyChildren(*this);
1583   if (!copy)
1584     copy = std::make_unique<DictionaryValue>();
1585   return copy;
1586 }
1587
1588 void DictionaryValue::Swap(DictionaryValue* other) {
1589   CHECK(other->is_dict());
1590   dict_.swap(other->dict_);
1591 }
1592
1593 DictionaryValue::Iterator::Iterator(const DictionaryValue& target)
1594     : target_(target), it_(target.dict_.begin()) {}
1595
1596 DictionaryValue::Iterator::Iterator(const Iterator& other) = default;
1597
1598 DictionaryValue::Iterator::~Iterator() = default;
1599
1600 DictionaryValue* DictionaryValue::DeepCopy() const {
1601   return new DictionaryValue(dict_);
1602 }
1603
1604 std::unique_ptr<DictionaryValue> DictionaryValue::CreateDeepCopy() const {
1605   return std::make_unique<DictionaryValue>(dict_);
1606 }
1607
1608 ///////////////////// ListValue ////////////////////
1609
1610 // static
1611 std::unique_ptr<ListValue> ListValue::From(std::unique_ptr<Value> value) {
1612   ListValue* out;
1613   if (value && value->GetAsList(&out)) {
1614     ignore_result(value.release());
1615     return WrapUnique(out);
1616   }
1617   return nullptr;
1618 }
1619
1620 ListValue::ListValue() : Value(Type::LIST) {}
1621 ListValue::ListValue(span<const Value> in_list) : Value(in_list) {}
1622 ListValue::ListValue(ListStorage&& in_list) noexcept
1623     : Value(std::move(in_list)) {}
1624
1625 void ListValue::Clear() {
1626   list_.clear();
1627 }
1628
1629 void ListValue::Reserve(size_t n) {
1630   list_.reserve(n);
1631 }
1632
1633 bool ListValue::Set(size_t index, std::unique_ptr<Value> in_value) {
1634   if (!in_value)
1635     return false;
1636
1637   if (index >= list_.size())
1638     list_.resize(index + 1);
1639
1640   list_[index] = std::move(*in_value);
1641   return true;
1642 }
1643
1644 bool ListValue::Get(size_t index, const Value** out_value) const {
1645   if (index >= list_.size())
1646     return false;
1647
1648   if (out_value)
1649     *out_value = &list_[index];
1650
1651   return true;
1652 }
1653
1654 bool ListValue::Get(size_t index, Value** out_value) {
1655   return as_const(*this).Get(index, const_cast<const Value**>(out_value));
1656 }
1657
1658 bool ListValue::GetBoolean(size_t index, bool* bool_value) const {
1659   const Value* value;
1660   if (!Get(index, &value))
1661     return false;
1662
1663   return value->GetAsBoolean(bool_value);
1664 }
1665
1666 bool ListValue::GetInteger(size_t index, int* out_value) const {
1667   const Value* value;
1668   if (!Get(index, &value))
1669     return false;
1670
1671   return value->GetAsInteger(out_value);
1672 }
1673
1674 bool ListValue::GetDouble(size_t index, double* out_value) const {
1675   const Value* value;
1676   if (!Get(index, &value))
1677     return false;
1678
1679   return value->GetAsDouble(out_value);
1680 }
1681
1682 bool ListValue::GetString(size_t index, std::string* out_value) const {
1683   const Value* value;
1684   if (!Get(index, &value))
1685     return false;
1686
1687   return value->GetAsString(out_value);
1688 }
1689
1690 bool ListValue::GetString(size_t index, string16* out_value) const {
1691   const Value* value;
1692   if (!Get(index, &value))
1693     return false;
1694
1695   return value->GetAsString(out_value);
1696 }
1697
1698 bool ListValue::GetDictionary(size_t index,
1699                               const DictionaryValue** out_value) const {
1700   const Value* value;
1701   bool result = Get(index, &value);
1702   if (!result || !value->is_dict())
1703     return false;
1704
1705   if (out_value)
1706     *out_value = static_cast<const DictionaryValue*>(value);
1707
1708   return true;
1709 }
1710
1711 bool ListValue::GetDictionary(size_t index, DictionaryValue** out_value) {
1712   return as_const(*this).GetDictionary(
1713       index, const_cast<const DictionaryValue**>(out_value));
1714 }
1715
1716 bool ListValue::GetList(size_t index, const ListValue** out_value) const {
1717   const Value* value;
1718   bool result = Get(index, &value);
1719   if (!result || !value->is_list())
1720     return false;
1721
1722   if (out_value)
1723     *out_value = static_cast<const ListValue*>(value);
1724
1725   return true;
1726 }
1727
1728 bool ListValue::GetList(size_t index, ListValue** out_value) {
1729   return as_const(*this).GetList(index,
1730                                  const_cast<const ListValue**>(out_value));
1731 }
1732
1733 bool ListValue::Remove(size_t index, std::unique_ptr<Value>* out_value) {
1734   if (index >= list_.size())
1735     return false;
1736
1737   if (out_value)
1738     *out_value = std::make_unique<Value>(std::move(list_[index]));
1739
1740   list_.erase(list_.begin() + index);
1741   return true;
1742 }
1743
1744 bool ListValue::Remove(const Value& value, size_t* index) {
1745   auto it = std::find(list_.begin(), list_.end(), value);
1746
1747   if (it == list_.end())
1748     return false;
1749
1750   if (index)
1751     *index = std::distance(list_.begin(), it);
1752
1753   list_.erase(it);
1754   return true;
1755 }
1756
1757 ListValue::iterator ListValue::Erase(iterator iter,
1758                                      std::unique_ptr<Value>* out_value) {
1759   if (out_value)
1760     *out_value = std::make_unique<Value>(std::move(*iter));
1761
1762   auto list_iter = list_.begin() + (iter - GetList().begin());
1763   CHECK(list_iter != list_.end());
1764   list_iter = list_.erase(list_iter);
1765   return GetList().begin() + (list_iter - list_.begin());
1766 }
1767
1768 void ListValue::Append(std::unique_ptr<Value> in_value) {
1769   list_.push_back(std::move(*in_value));
1770 }
1771
1772 void ListValue::AppendBoolean(bool in_value) {
1773   list_.emplace_back(in_value);
1774 }
1775
1776 void ListValue::AppendInteger(int in_value) {
1777   list_.emplace_back(in_value);
1778 }
1779
1780 void ListValue::AppendDouble(double in_value) {
1781   list_.emplace_back(in_value);
1782 }
1783
1784 void ListValue::AppendString(StringPiece in_value) {
1785   list_.emplace_back(in_value);
1786 }
1787
1788 void ListValue::AppendString(const string16& in_value) {
1789   list_.emplace_back(in_value);
1790 }
1791
1792 void ListValue::AppendStrings(const std::vector<std::string>& in_values) {
1793   list_.reserve(list_.size() + in_values.size());
1794   for (const auto& in_value : in_values)
1795     list_.emplace_back(in_value);
1796 }
1797
1798 void ListValue::AppendStrings(const std::vector<string16>& in_values) {
1799   list_.reserve(list_.size() + in_values.size());
1800   for (const auto& in_value : in_values)
1801     list_.emplace_back(in_value);
1802 }
1803
1804 bool ListValue::AppendIfNotPresent(std::unique_ptr<Value> in_value) {
1805   DCHECK(in_value);
1806   if (Contains(list_, *in_value))
1807     return false;
1808
1809   list_.push_back(std::move(*in_value));
1810   return true;
1811 }
1812
1813 bool ListValue::Insert(size_t index, std::unique_ptr<Value> in_value) {
1814   DCHECK(in_value);
1815   if (index > list_.size())
1816     return false;
1817
1818   list_.insert(list_.begin() + index, std::move(*in_value));
1819   return true;
1820 }
1821
1822 ListValue::const_iterator ListValue::Find(const Value& value) const {
1823   return std::find(GetList().begin(), GetList().end(), value);
1824 }
1825
1826 void ListValue::Swap(ListValue* other) {
1827   CHECK(other->is_list());
1828   list_.swap(other->list_);
1829 }
1830
1831 ListValue* ListValue::DeepCopy() const {
1832   return new ListValue(list_);
1833 }
1834
1835 std::unique_ptr<ListValue> ListValue::CreateDeepCopy() const {
1836   return std::make_unique<ListValue>(list_);
1837 }
1838
1839 ValueSerializer::~ValueSerializer() = default;
1840
1841 ValueDeserializer::~ValueDeserializer() = default;
1842
1843 std::ostream& operator<<(std::ostream& out, const Value& value) {
1844   std::string json;
1845   JSONWriter::WriteWithOptions(value, JSONWriter::OPTIONS_PRETTY_PRINT, &json);
1846   return out << json;
1847 }
1848
1849 std::ostream& operator<<(std::ostream& out, const Value::Type& type) {
1850   if (static_cast<int>(type) < 0 ||
1851       static_cast<size_t>(type) >= base::size(kTypeNames))
1852     return out << "Invalid Type (index = " << static_cast<int>(type) << ")";
1853   return out << Value::GetTypeName(type);
1854 }
1855
1856 }  // namespace base