[lldb][NFCI] Remove use of ConstString in StructuredData

[bulbazord]

Summary

The remaining use of ConstString in StructuredData is the Dictionary
class. Internally it's backed by a std::map<ConstString, ObjectSP>.
I propose that we replace it with a llvm::StringMap<ObjectSP>.

Many StructuredData::Dictionary objects are ephemeral and only exist for
a short amount of time. Many of these Dictionaries are only produced
once and are never used again. That leaves us with a lot of string data
in the ConstString StringPool that is sitting there never to be used
again. Even if the same string is used many times for keys of different
Dictionary objects, that is something we can measure and adjust for
instead of assuming that every key may be reused at some point in the
future.

Quick comparisons of key data is likely not a concern with Dictionary,
but the use of llvm::StringMap means that lookups should be fast with
its hashing strategy.

Switching to a llvm::StringMap meant that the iteration order may be
different. To account for this when serializing/dumping the dictionary,
I added some code to sort the output by key before emitting anything.

[fdeazeve]

lldb/include/lldb/Utility/StructuredData.h

436

Since we are touching this line anyway, could you replace this with

for (StringRef key : llvm::make_first_range(m_dict))

This has a bit less cognitive burden IMO

438

Also since you are touching this line, one could argue for it to be deleted and folded into std::make_shared<String>(Key);

I don't feel strongly about it though, it could also be more appropriate for a separate commit

448

This line in particular also shows why I think this patch is appropriate: even queries were introducing strings into the pool

537

This is not equivalent to the old code, right? The previous code would overwrite the contents if the key already existed.

lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp

2035

This is another win: the old code was calling StringRef(const char*), which has to iterate over the entire string to find the null terminating character.

lldb/source/Plugins/SymbolVendor/MacOSX/SymbolVendorMacOSX.cpp

248

same win here

lldb/source/Target/Target.cpp

3866

we talked about it in private, but I feel like stating this publicly: does anyone know if this was legal? object->GetStringValue().str() creates a temporary std::string. And then we call c_str() and pass that to the Printf function. Does the temporary std::string have its lifetime extended?

lldb/source/Utility/StructuredData.cpp

173

I thought pairs had operator < defined already?

[bulbazord]

lldb/include/lldb/Utility/StructuredData.h

448

Yes, this also was happening in HasKey as well.

537

Oh, good catch. I think what I want is insert_or_assign. Will update.

lldb/source/Utility/StructuredData.cpp

173

Oh, I didn't even think to check. I'll try it and update if I don't need to define this lambda.

[bulbazord]

Address feedback from @fdeazeve

lldb/include/lldb/Utility/StructuredData.h

436

Unfortunately no, llvm::make_first_range assumes that you can refer to first on an iterator, but first is actually a method to be called. The iterator code will have to stay for now.

[bulbazord]

lldb/source/Utility/StructuredData.cpp

251–253

Oh I can remove this lambda too -- Let me update.

[bulbazord]

Remove unneeded lambda

[fdeazeve]

LGTM!

lldb/include/lldb/Utility/StructuredData.h

 //===-- StructuredData.h ----------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_UTILITY_STRUCTUREDDATA_H
 #define LLDB_UTILITY_STRUCTUREDDATA_H
 
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/JSON.h"
 
-#include "lldb/Utility/ConstString.h"
 #include "lldb/Utility/FileSpec.h"
 #include "lldb/Utility/Stream.h"
 #include "lldb/lldb-enumerations.h"
 
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <functional>
Dictionary(ObjectSP obj_sp) : Object(lldb::eStructuredDataTypeDictionary) {
       Dictionary *dict = obj_sp->GetAsDictionary();
       m_dict = dict->m_dict;
     }
 
     ~Dictionary() override = default;
 
     size_t GetSize() const { return m_dict.size(); }
 
-    void ForEach(std::function<bool(ConstString key, Object *object)> const
+    void ForEach(std::function<bool(llvm::StringRef key, Object *object)> const
                      &callback) const {
       for (const auto &pair : m_dict) {
-        if (!callback(pair.first, pair.second.get()))
+        if (!callback(pair.first(), pair.second.get()))
           break;
       }
     }
 
     ArraySP GetKeys() const {
       auto array_sp = std::make_shared<Array>();
-      collection::const_iterator iter;
-      for (iter = m_dict.begin(); iter != m_dict.end(); ++iter) {
+      for (auto iter = m_dict.begin(); iter != m_dict.end(); ++iter) {
         auto key_object_sp = std::make_shared<String>();
-        key_object_sp->SetValue(iter->first.AsCString());
+        key_object_sp->SetValue(iter->first());
         array_sp->Push(key_object_sp);
       }
       return array_sp;
     }
 
     ObjectSP GetValueForKey(llvm::StringRef key) const {
-      ObjectSP value_sp;
-      if (!key.empty()) {
-        ConstString key_cs(key);
-        collection::const_iterator iter = m_dict.find(key_cs);
-        if (iter != m_dict.end())
-          value_sp = iter->second;
-      }
-      return value_sp;
+      return m_dict.lookup(key);
     }
 
     bool GetValueForKeyAsBoolean(llvm::StringRef key, bool &result) const {
       bool success = false;
       ObjectSP value_sp = GetValueForKey(key);
       if (value_sp.get()) {
         Boolean *result_ptr = value_sp->GetAsBoolean();
         if (result_ptr) {
bool GetValueForKeyAsArray(llvm::StringRef key, Array *&result) const {
       ObjectSP value_sp = GetValueForKey(key);
       if (value_sp.get()) {
         result = value_sp->GetAsArray();
         return (result != nullptr);
       }
       return false;
     }
 
-    bool HasKey(llvm::StringRef key) const {
-      ConstString key_cs(key);
-      collection::const_iterator search = m_dict.find(key_cs);
-      return search != m_dict.end();
-    }
+    bool HasKey(llvm::StringRef key) const { return m_dict.contains(key); }
 
     void AddItem(llvm::StringRef key, ObjectSP value_sp) {
-      ConstString key_cs(key);
-      m_dict[key_cs] = std::move(value_sp);
+      m_dict.insert({key, std::move(value_sp)});
     }
 
     template <typename T> void AddIntegerItem(llvm::StringRef key, T value) {
       static_assert(std::is_integral<T>::value ||
                         std::is_floating_point<T>::value,
                     "value type should be integral");
       if constexpr (std::numeric_limits<T>::is_signed)
         AddItem(key, std::make_shared<SignedInteger>(value));
void AddBooleanItem(llvm::StringRef key, bool value) {
       AddItem(key, std::make_shared<Boolean>(value));
     }
 
     void Serialize(llvm::json::OStream &s) const override;
 
     void GetDescription(lldb_private::Stream &s) const override;
 
   protected:
-    typedef std::map<ConstString, ObjectSP> collection;
-    collection m_dict;
+    llvm::StringMap<ObjectSP> m_dict;
   };
 
   class Null : public Object {
   public:
     Null() : Object(lldb::eStructuredDataTypeNull) {}
 
     ~Null() override = default;
 

lldb/source/Plugins/Platform/MacOSX/PlatformDarwin.cpp

PlatformDarwin::ExtractAppSpecificInfo(Process &process) {
 
   StructuredData::Dictionary *asi;
   if (!metadata_sp->GetValueForKeyAsDictionary("asi", asi))
     return {};
 
   StructuredData::DictionarySP dict_sp =
       std::make_shared<StructuredData::Dictionary>();
 
-  auto flatten_asi_dict = [&dict_sp](ConstString key,
+  auto flatten_asi_dict = [&dict_sp](llvm::StringRef key,
                                      StructuredData::Object *val) -> bool {
     if (!val)
       return false;
 
     StructuredData::Array *arr = val->GetAsArray();
     if (!arr || !arr->GetSize())
       return false;
 
-    dict_sp->AddItem(key.AsCString(), arr->GetItemAtIndex(0));
+    dict_sp->AddItem(key, arr->GetItemAtIndex(0));
     return true;
   };
 
   asi->ForEach(flatten_asi_dict);
 
   return dict_sp;
 }
 

lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp

if (exc_type != 0) {
       }
     }
   }
   return thread_sp;
 }
 
 lldb::ThreadSP
 ProcessGDBRemote::SetThreadStopInfo(StructuredData::Dictionary *thread_dict) {
-  static ConstString g_key_tid("tid");
-  static ConstString g_key_name("name");
-  static ConstString g_key_reason("reason");
-  static ConstString g_key_metype("metype");
-  static ConstString g_key_medata("medata");
-  static ConstString g_key_qaddr("qaddr");
-  static ConstString g_key_dispatch_queue_t("dispatch_queue_t");
-  static ConstString g_key_associated_with_dispatch_queue(
+  static constexpr llvm::StringLiteral g_key_tid("tid");
+  static constexpr llvm::StringLiteral g_key_name("name");
+  static constexpr llvm::StringLiteral g_key_reason("reason");
+  static constexpr llvm::StringLiteral g_key_metype("metype");
+  static constexpr llvm::StringLiteral g_key_medata("medata");
+  static constexpr llvm::StringLiteral g_key_qaddr("qaddr");
+  static constexpr llvm::StringLiteral g_key_dispatch_queue_t(
+      "dispatch_queue_t");
+  static constexpr llvm::StringLiteral g_key_associated_with_dispatch_queue(
       "associated_with_dispatch_queue");
-  static ConstString g_key_queue_name("qname");
-  static ConstString g_key_queue_kind("qkind");
-  static ConstString g_key_queue_serial_number("qserialnum");
-  static ConstString g_key_registers("registers");
-  static ConstString g_key_memory("memory");
-  static ConstString g_key_address("address");
-  static ConstString g_key_bytes("bytes");
-  static ConstString g_key_description("description");
-  static ConstString g_key_signal("signal");
+  static constexpr llvm::StringLiteral g_key_queue_name("qname");
+  static constexpr llvm::StringLiteral g_key_queue_kind("qkind");
+  static constexpr llvm::StringLiteral g_key_queue_serial_number("qserialnum");
+  static constexpr llvm::StringLiteral g_key_registers("registers");
+  static constexpr llvm::StringLiteral g_key_memory("memory");
+  static constexpr llvm::StringLiteral g_key_description("description");
+  static constexpr llvm::StringLiteral g_key_signal("signal");
 
   // Stop with signal and thread info
   lldb::tid_t tid = LLDB_INVALID_THREAD_ID;
   uint8_t signo = 0;
   std::string value;
   std::string thread_name;
   std::string reason;
   std::string description;
ProcessGDBRemote::SetThreadStopInfo(StructuredData::Dictionary *thread_dict) {
   // structured data dictionary
 
   // FIXME: we're silently ignoring invalid data here
   thread_dict->ForEach([this, &tid, &expedited_register_map, &thread_name,
                         &signo, &reason, &description, &exc_type, &exc_data,
                         &thread_dispatch_qaddr, &queue_vars_valid,
                         &associated_with_dispatch_queue, &dispatch_queue_t,
                         &queue_name, &queue_kind, &queue_serial_number](
-                           ConstString key,
+                           llvm::StringRef key,
                            StructuredData::Object *object) -> bool {
     if (key == g_key_tid) {
       // thread in big endian hex
       tid = object->GetUnsignedIntegerValue(LLDB_INVALID_THREAD_ID);
     } else if (key == g_key_metype) {
       // exception type in big endian hex
       exc_type = object->GetUnsignedIntegerValue(0);
     } else if (key == g_key_medata) {
if (key == g_key_tid) {
       reason = std::string(object->GetStringValue());
     } else if (key == g_key_description) {
       description = std::string(object->GetStringValue());
     } else if (key == g_key_registers) {
       StructuredData::Dictionary *registers_dict = object->GetAsDictionary();
 
       if (registers_dict) {
         registers_dict->ForEach(
-            [&expedited_register_map](ConstString key,
+            [&expedited_register_map](llvm::StringRef key,
                                       StructuredData::Object *object) -> bool {
               uint32_t reg;
-              if (llvm::to_integer(key.AsCString(), reg))
+              if (llvm::to_integer(key, reg))
                 expedited_register_map[reg] =
                     std::string(object->GetStringValue());
               return true; // Keep iterating through all array items
             });
       }
     } else if (key == g_key_memory) {
       StructuredData::Array *array = object->GetAsArray();
       if (array) {

lldb/source/Plugins/SymbolVendor/MacOSX/SymbolVendorMacOSX.cpp

if (dsym_fspec) {
                       StructuredData::Dictionary *remappings_dict =
                           plist_sp->GetAsDictionary()
                               ->GetValueForKey("DBGSourcePathRemapping")
                               ->GetAsDictionary();
                       remappings_dict->ForEach(
                           [&module_sp, new_style_source_remapping_dictionary,
                            original_DBGSourcePath_value,
                            do_truncate_remapping_names](
-                              ConstString key,
+                              llvm::StringRef key,
                               StructuredData::Object *object) -> bool {
                             if (object && object->GetAsString()) {
 
                               // key is DBGBuildSourcePath
                               // object is DBGSourcePath
                               std::string DBGSourcePath =
                                   std::string(object->GetStringValue());
                               if (!new_style_source_remapping_dictionary &&
                                   !original_DBGSourcePath_value.empty()) {
                                 DBGSourcePath = original_DBGSourcePath_value;
                               }
                               module_sp->GetSourceMappingList().Append(
-                                  key.GetStringRef(), DBGSourcePath, true);
+                                  key, DBGSourcePath, true);
                               // With version 2 of DBGSourcePathRemapping, we
                               // can chop off the last two filename parts
                               // from the source remapping and get a more
                               // general source remapping that still works.
                               // Add this as another option in addition to
                               // the full source path remap.
                               if (do_truncate_remapping_names) {
-                                FileSpec build_path(key.AsCString());
+                                FileSpec build_path(key);
                                 FileSpec source_path(DBGSourcePath.c_str());
                                 build_path.RemoveLastPathComponent();
                                 build_path.RemoveLastPathComponent();
                                 source_path.RemoveLastPathComponent();
                                 source_path.RemoveLastPathComponent();
                                 module_sp->GetSourceMappingList().Append(
                                     build_path.GetPath(), source_path.GetPath(),
                                     true);

lldb/source/Target/Target.cpp

void Target::StopHookScripted::GetSubclassDescription(
 
   uint32_t num_keys = as_dict->GetSize();
   if (num_keys == 0)
     return;
 
   s.Indent("Args:\n");
   s.SetIndentLevel(s.GetIndentLevel() + 4);
 
-  auto print_one_element = [&s](ConstString key,
+  auto print_one_element = [&s](llvm::StringRef key,
                                 StructuredData::Object *object) {
     s.Indent();
-    s.Printf("%s : %s\n", key.GetCString(),
-              object->GetStringValue().str().c_str());
+    s.Format("{0} : {1}\n", key, object->GetStringValue());
     return true;
   };
 
   as_dict->ForEach(print_one_element);
 
   s.SetIndentLevel(s.GetIndentLevel() - 4);
 }
 

lldb/source/Utility/StructuredData.cpp

 }
 
 void StructuredData::String::Serialize(json::OStream &s) const {
   s.value(m_value);
 }
 
 void StructuredData::Dictionary::Serialize(json::OStream &s) const {
   s.objectBegin();
-  for (const auto &pair : m_dict) {
-    s.attributeBegin(pair.first.GetStringRef());
+
+  // To ensure the output format is always stable, we sort the dictionary by key
+  // first.
+  using Entry = std::pair<llvm::StringRef, ObjectSP>;
+  std::vector<Entry> sorted_entries;
+  for (const auto &pair : m_dict)
+    sorted_entries.push_back({pair.first(), pair.second});
+
+  llvm::sort(sorted_entries, [&](const Entry &lhs, const Entry &rhs) -> bool {
+    return lhs.first < rhs.first;
+  });
+
+  for (const auto &pair : sorted_entries) {
+    s.attributeBegin(pair.first);
     pair.second->Serialize(s);
     s.attributeEnd();
   }
   s.objectEnd();
 }
 
 void StructuredData::Null::Serialize(json::OStream &s) const {
   s.value(nullptr);
for (const auto &item_sp : m_items) {
     // Reset indentation level if it was incremented previously.
     if (should_indent)
       s.IndentLess();
   }
 }
 
 void StructuredData::Dictionary::GetDescription(lldb_private::Stream &s) const {
   size_t indentation_level = s.GetIndentLevel();
-  for (auto iter = m_dict.begin(); iter != m_dict.end(); iter++) {
+
+  // To ensure the output format is always stable, we sort the dictionary by key
+  // first.
+  using Entry = std::pair<llvm::StringRef, ObjectSP>;
+  std::vector<Entry> sorted_entries;
+  for (const auto &pair : m_dict)
+    sorted_entries.push_back({pair.first(), pair.second});
+
+  llvm::sort(sorted_entries, [&](const Entry &lhs, const Entry &rhs) -> bool {
+    return lhs.first < rhs.first;
+  });
+
+  for (auto iter = sorted_entries.begin(); iter != sorted_entries.end();
+       iter++) {
     // Sanitize.
-    if (iter->first.IsNull() || iter->first.IsEmpty() || !iter->second)
+    if (iter->first.empty() || !iter->second)
       continue;
 
     // Reset original indentation level.
     s.SetIndentLevel(indentation_level);
     s.Indent();
 
     // Print key.
-    s.Printf("%s:", iter->first.AsCString());
+    s.Format("{0}:", iter->first);
 
     // Return to new line and increase indentation if value is record type.
     // Otherwise add spacing.
     bool should_indent = IsRecordType(iter->second);
     if (should_indent) {
       s.EOL();
       s.IndentMore();
     } else {
       s.PutChar(' ');
     }
 
     // Print value and new line if now last pair.
     iter->second->GetDescription(s);
-    if (std::next(iter) != m_dict.end())
+    if (std::next(iter) != sorted_entries.end())
       s.EOL();
 
     // Reset indentation level if it was incremented previously.
     if (should_indent)
       s.IndentLess();
   }
 }
 
 void StructuredData::Null::GetDescription(lldb_private::Stream &s) const {
   s.Printf("NULL");
 }
 
 void StructuredData::Generic::GetDescription(lldb_private::Stream &s) const {
   s.Printf("%p", m_object);
 }