[lldb/Plugin] Sort the ScriptedProcess' thread list before creating threads

[mib]

Summary

With Scripted Processes, in order to create scripted threads, the blueprint
provides a dictionary that have each thread index as the key with the respective
thread instance as the pair value.

In Python, this is fine because a dictionary key can be of any type including
integer types:

>>> {1: "one", 2: "two", 10: "ten"}
{1: 'one', 2: 'two', 10: 'ten'}

However, when the python dictionary gets bridged to C++ with convert it to a
StructuredData::Dictionary that uses a std::map<ConstString, ObjectSP>
for storage.

Because std::map is an ordered container and ours uses the ConstString
type for keys, the thread indices gets converted to strings which makes the
dictionary sorted alphabetically, instead of numerically.

If the ScriptedProcesse has 10 threads or more, it causes thread “10”
(and higher) to be after thread “1”, but before thread “2”.

In order to solve this, this sorts the thread info dictionary keys
numerically, before iterating over them to create ScriptedThreads.

rdar://90327854

Signed-off-by: Med Ismail Bennani <[e-mail]>

[JDevlieghere]

lldb/source/Plugins/Process/scripted/ScriptedProcess.cpp

352

Won't this overflow when you return the example from the summary?

{1: "one", 2: "two", 10: "ten"}

Would it be easier to populate our own map<size_t, ObjectSP> and iterate over that below?

[mib]

lldb/source/Plugins/Process/scripted/ScriptedProcess.cpp

352

I don't see why it would overflow 🧐

[JDevlieghere]

lldb/source/Plugins/Process/scripted/ScriptedProcess.cpp

352

You create a vector with 3 elements:

std::vector<llvm::StringRef> sorted_keys(keys->GetSize());

But you use the key from the dictionary to index the vector:

sorted_keys[0] = "";
sorted_keys[1] = "one";
sorted_keys[2] = "two";
-- end of vector --
sorted_keys[10] = "ten";

[mib]

lldb/source/Plugins/Process/scripted/ScriptedProcess.cpp

352

You're right! I didn't hit this because in the Scripted Process case, indices are 0 based, so that works perfectly but I guess I could use a map to prevent a potential overflow

[mib]

Implement @JDevlieghere suggestions:

• Use a std::map<size_t, ObjectSP> to sort the thread info dictionary to prevent potential overflows

[JDevlieghere]

lldb/source/Plugins/Process/scripted/ScriptedProcess.cpp

321–342

Instead of this callback, can we simplify the code by iterating over the keys and populate the map that way?

[mib]

lldb/source/Plugins/Process/scripted/ScriptedProcess.cpp

321–342

We don't have iterators to iterate over StructuredData containers with a range-based loop, so we can only iterate over them using indices ...

I find it ungracious to do it that way because we have to call GetItemAtIndex(idx) to get the StructuredData::Object element from the array, that's why I used the ForEach method instead.

I think we can improve StructuredData containers to be more customizable and operate better with the std/adl utilities, it should be done separately.

[mib]

lldb/source/Plugins/Process/scripted/ScriptedProcess.cpp

321–342

I think we've discussed this offline, but if we made the StructuredData::Array templated (with a default template parameter), we could prevent having to sort ourself the thread dictionary, and loop twice over it (which annoys me quite a bit 😅😅)

[JDevlieghere]

LGMT

lldb/source/Plugins/Process/scripted/ScriptedProcess.cpp

321–342

Okay, that's unfortunate. Thanks for the explanation!

lldb/source/Plugins/Process/scripted/ScriptedProcess.cpp

return ScriptedInterface::ErrorWithMessage<bool>(
         llvm::Twine("ScriptInterpreter language (" +
                     llvm::Twine(m_interpreter->LanguageToString(language)) +
                     llvm::Twine(") not supported."))
             .str(),
         error);
 
   StructuredData::DictionarySP thread_info_sp = GetInterface().GetThreadsInfo();
 
-  // FIXME: Need to sort the dictionary otherwise the thread ids won't match the
-  // thread indices.
-
   if (!thread_info_sp)
     return ScriptedInterface::ErrorWithMessage<bool>(
         LLVM_PRETTY_FUNCTION,
         "Couldn't fetch thread list from Scripted Process.", error);
 
-  auto create_scripted_thread =
-      [this, &old_thread_list, &error,
-       &new_thread_list](ConstString key, StructuredData::Object *val) -> bool {
-    if (!val)
-      return ScriptedInterface::ErrorWithMessage<bool>(
-          LLVM_PRETTY_FUNCTION, "Invalid thread info object", error);
+  // Because `StructuredData::Dictionary` uses a `std::map<ConstString,
+  // ObjectSP>` for storage, each item is sorted based on the key alphabetical
+  // order. Since `GetThreadsInfo` provides thread indices as the key element,
+  // thread info comes ordered alphabetically, instead of numerically, so we
+  // need to sort the thread indices before creating thread.
+
+  StructuredData::ArraySP keys = thread_info_sp->GetKeys();
+
+  std::map<size_t, StructuredData::ObjectSP> sorted_threads;
+  auto sort_keys = [&sorted_threads,
+                    &thread_info_sp](StructuredData::Object *item) -> bool {
+    if (!item)
+      return false;
 
-    lldb::tid_t tid = LLDB_INVALID_THREAD_ID;
-    if (!llvm::to_integer(key.AsCString(), tid))
-      return ScriptedInterface::ErrorWithMessage<bool>(
-          LLVM_PRETTY_FUNCTION, "Invalid thread id", error);
+    llvm::StringRef key = item->GetStringValue();
+    size_t idx = 0;
 
-    if (ThreadSP thread_sp =
-            old_thread_list.FindThreadByID(tid, false /*=can_update*/)) {
-      // If the thread was already in the old_thread_list,
-      // just add it back to the new_thread_list.
-      new_thread_list.AddThread(thread_sp);
-      return true;
-    }
+    // Make sure the provided index is actually an integer
+    if (!llvm::to_integer(key, idx))
+      return false;
+
+    sorted_threads[idx] = thread_info_sp->GetValueForKey(key);
+  };
+
+  size_t thread_count = thread_info_sp->GetSize();
+
+  if (!keys->ForEach(sort_keys) || sorted_threads.size() != thread_count)
+    // Might be worth showing the unsorted thread list instead of return early.
+    return ScriptedInterface::ErrorWithMessage<bool>(
+        LLVM_PRETTY_FUNCTION, "Couldn't sort thread list.", error);
+
+  auto create_scripted_thread =
+      [this, &error, &new_thread_list](
+          const std::pair<size_t, StructuredData::ObjectSP> pair) -> bool {
+    size_t idx = pair.first;
+    StructuredData::ObjectSP object_sp = pair.second;
+
+    if (!object_sp)
+      return ScriptedInterface::ErrorWithMessage<bool>(
+          LLVM_PRETTY_FUNCTION, "Invalid thread info object", error);
 
-    auto thread_or_error = ScriptedThread::Create(*this, val->GetAsGeneric());
+    auto thread_or_error =
+        ScriptedThread::Create(*this, object_sp->GetAsGeneric());
 
     if (!thread_or_error)
       return ScriptedInterface::ErrorWithMessage<bool>(
           LLVM_PRETTY_FUNCTION, toString(thread_or_error.takeError()), error);
 
     ThreadSP thread_sp = thread_or_error.get();
     lldbassert(thread_sp && "Couldn't initialize scripted thread.");
 
     RegisterContextSP reg_ctx_sp = thread_sp->GetRegisterContext();
     if (!reg_ctx_sp)
       return ScriptedInterface::ErrorWithMessage<bool>(
           LLVM_PRETTY_FUNCTION,
-          llvm::Twine("Invalid Register Context for thread " +
-                      llvm::Twine(key.AsCString()))
+          llvm::Twine("Invalid Register Context for thread " + llvm::Twine(idx))
               .str(),
           error);
 
     new_thread_list.AddThread(thread_sp);
 
     return true;
   };
 
-  thread_info_sp->ForEach(create_scripted_thread);
+  llvm::for_each(sorted_threads, create_scripted_thread);
 
   return new_thread_list.GetSize(false) > 0;
 }
 
 void ScriptedProcess::RefreshStateAfterStop() {
   // Let all threads recover from stopping and do any clean up based on the
   // previous thread state (if any).
   m_thread_list.RefreshStateAfterStop();