[llvm][utils] Add DenseMap data formatters

[kastiglione]

Summary

Add summary and synthetic data formatters for llvm::DenseMap.

This implementation avoids expression evaluation by using a heuristic. However, as heuristics go, there is a corner case: A single deleted entry (a single "tombstone"), will result in a child value with an invalid key but a valid value.

Instead of using getEmptyKey() and getTombstoneKey() to determine which buckets are empty, and which contain real key-values, the heuristic scans all buckets to identify keys that exist only once. These singleton keys are considered valid.

The empty key will always exist multiple times. However the tombstone key may exist zero, one, or many times. The heuristic has no problems when there are zero or many tombstones, but when there is exactly one deleted entry (one tombstone), then the heuristic will incorrectly identify it as valid.

[kastiglione]

I'm open to better ways of doing this!

I have an idea of an additional heuristic to handle the case where there's one tombstone. Before I explain it I will see what ideas others have.

[aprantl]

I really like that this doesn't run expressions!

llvm/utils/lldbDataFormatters.py

328

.

330

else error?

347

typo

362

heuristic

[kastiglione]

llvm/utils/lldbDataFormatters.py

330

I'll add a comment about this being a nice-to-have unwrapping.

Instances of DenseMap can specify a custom alternative to DenseMapPair. In that case, this formatter will return children as-is, since it doesn't know anything about the custom type.

[kastiglione]

Elaborate comment, fix typos, reformat.

[kastiglione]

Fix summary provider by working with the non-synthetic value

[kastiglione]

Change get_child_at_index return type to non-Optional

[kastiglione]

• Add logic to recognize DenseSet, in which case all buckets are printed
• Change the summary to call out when a single tombstone is present in the children

[kastiglione]

Fix range(N) to list(range(N))

[kastiglione]

Remove the DenseSet logic, which I had wrong

[Michael137]

llvm/utils/lldbDataFormatters.py

18

Was playing around with this patch locally and it works quite well.

I had to add -e here though to get the children to display

[kastiglione]

Add -e to expand DenseMap children

[kastiglione]

@Michael137 I'll wait a week before merging, in case any issues arise in your usage. These days I haven't been crossing paths with many DenseMap instances, so my beta testing has been zero.

llvm/utils/lldbDataFormatters.py

 """
 LLDB Formatters for LLVM data types.
 
 Load into LLDB with 'command script import /path/to/lldbDataFormatters.py'
 """
 
+import collections
 import lldb
 import json
+from typing import Optional
+
 
 def __lldb_init_module(debugger, internal_dict):
     debugger.HandleCommand('type category define -e llvm -l c++')
     debugger.HandleCommand('type synthetic add -w llvm '
                            '-l lldbDataFormatters.SmallVectorSynthProvider '
                            '-x "^llvm::SmallVectorImpl<.+>$"')
     debugger.HandleCommand('type summary add -w llvm '
                            '-e -s "size=${svar%#}" '
                            '-x "^llvm::SmallVectorImpl<.+>$"')
     debugger.HandleCommand('type synthetic add -w llvm '
                            '-l lldbDataFormatters.SmallVectorSynthProvider '
                            '-x "^llvm::SmallVector<.+,.+>$"')
     debugger.HandleCommand('type summary add -w llvm '
                            '-e -s "size=${svar%#}" '
                            '-x "^llvm::SmallVector<.+,.+>$"')
debugger.HandleCommand('type summary add -w llvm '
                            '-F lldbDataFormatters.ConstStringSummaryProvider '
                            '-x "^lldb_private::ConstString$"')
     debugger.HandleCommand('type synthetic add -w llvm '
                            '-l lldbDataFormatters.PointerIntPairSynthProvider '
                            '-x "^llvm::PointerIntPair<.+>$"')
     debugger.HandleCommand('type synthetic add -w llvm '
                            '-l lldbDataFormatters.PointerUnionSynthProvider '
                            '-x "^llvm::PointerUnion<.+>$"')
+    debugger.HandleCommand('type summary add -w llvm '
+                           '-e -F lldbDataFormatters.DenseMapSummary '
+                           '-x "^llvm::DenseMap<.+>$"')
+    debugger.HandleCommand('type synthetic add -w llvm '
+                           '-l lldbDataFormatters.DenseMapSynthetic '
+                           '-x "^llvm::DenseMap<.+>$"')
 
 
 # Pretty printer for llvm::SmallVector/llvm::SmallVectorImpl
 class SmallVectorSynthProvider:
     def __init__(self, valobj, internal_dict):
         self.valobj = valobj
         self.update() # initialize this provider
 
def get_child_at_index(self, index):
         ptr_type_name = self.template_args[self.active_type_tag]
         return self.valobj.CreateValueFromExpression('Ptr', f'({ptr_type_name}){self.val_expr_path}.getPointer()')
 
     def update(self):
         self.pointer_int_pair = self.valobj.GetChildMemberWithName('Val')
         self.val_expr_path = get_expression_path(self.valobj.GetChildMemberWithName('Val'))
         self.active_type_tag = self.valobj.CreateValueFromExpression('', f'(int){self.val_expr_path}.getInt()').GetValueAsSigned()
         self.template_args = parse_template_parameters(self.valobj.GetType().name)
+
+
+def DenseMapSummary(valobj: lldb.SBValue, _) -> str:
+    num_entries = valobj.GetChildMemberWithName("NumEntries").unsigned
+    return f"size={num_entries}"
+
+
+class DenseMapSynthetic:
+    valobj: lldb.SBValue
+
+    # The bucket indexes containing child values.
+    child_buckets: list[int]
+
+    def __init__(self, valobj: lldb.SBValue, _) -> None:
+        self.valobj = valobj
+
+    def num_children(self) -> int:
+        return len(self.child_buckets)
+
+    def get_child_at_index(self, child_index: int) -> Optional[lldb.SBValue]:
+        bucket_index = self.child_buckets[child_index]
+        entry = self.valobj.GetValueForExpressionPath(f".Buckets[{bucket_index}]")
+
+        # By default, DenseMap instances use DenseMapPair to hold key-value
+        # entries. This type can be customized (it's a template parameter). If
+        # the entry is a DenseMapPair, unwrap it to expose the child entries as
+        # simple std::pair values. Otherwise, use the entry as is.
+        if entry.type.name.startswith("llvm::detail::DenseMapPair<"):
+            entry = entry.GetChildAtIndex(0)
+
+        return entry.Clone(f"[{child_index}]")
+
+    def get_child_index(self, name: str) -> Optional[lldb.SBValue]:
+        return None
+
+    def update(self) -> bool:
+        self.child_buckets = []
+
+        num_entries = self.valobj.GetChildMemberWithName("NumEntries").unsigned
+        if num_entries == 0:
+            return
+
+        buckets = self.valobj.GetChildMemberWithName("Buckets")
+        num_buckets = self.valobj.GetChildMemberWithName("NumBuckets").unsigned
+
+        # Bucket entries contain one of the following:
+        #   1. Valid key-value
+        #   2. Empty key
+        #   3. Tombstone key (marks a deleted value)
+        #
+        # NumBuckets is always greater than NumEntries. The empty key, and
+        # potentially the tombstone key, will occur multiple times. A key that
+        # is repeated is either the empty key or the tombstone key.
+
+        # For each key, collect a list of buckets it appears in.
+        key_buckets: dict[str, list[int]] = collections.defaultdict(list)
+        for index in range(num_buckets):
+            key = buckets.GetValueForExpressionPath(f"[{index}].first")
+            key_buckets[str(key.data)].append(index)
+
+        # Heuristic: Repeated (non-unique) keys are either the the empty key or
+        # the tombstone key. Populate child_buckets with the bucket indexes of
+        # entries containing unique keys.
+        for indexes in key_buckets.values():
+            if len(indexes) == 1:
+                self.child_buckets.append(indexes[0])
+
+        return True