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