This is an archive of the discontinued LLVM Phabricator instance.

[llvm][utils] Add DenseMap data formatters
ClosedPublic

Authored by kastiglione on Oct 29 2022, 3:24 PM.

Details

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.

Diff Detail

Event Timeline

kastiglione created this revision.Oct 29 2022, 3:24 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 29 2022, 3:24 PM
kastiglione requested review of this revision.Oct 29 2022, 3:24 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 29 2022, 3:24 PM

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.

I really like that this doesn't run expressions!

llvm/utils/lldbDataFormatters.py
328

.

330

else error?

347

typo

362

heuristic

kastiglione added inline comments.Nov 10 2022, 3:48 PM
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.

Elaborate comment, fix typos, reformat.

aprantl accepted this revision.Nov 10 2022, 4:39 PM
This revision is now accepted and ready to land.Nov 10 2022, 4:39 PM

Fix summary provider by working with the non-synthetic value

kastiglione marked an inline comment as done.

Change get_child_at_index return type to non-Optional

kastiglione retitled this revision from [llvm][utils] Add DenseMap data formatters (WIP) to [llvm][utils] Add DenseMap data formatters.Nov 11 2022, 4:09 PM
  • 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

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

Remove the DenseSet logic, which I had wrong

Michael137 added inline comments.Jul 12 2023, 5:01 AM
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

Add -e to expand DenseMap children

kastiglione marked an inline comment as done.Jul 12 2023, 10:27 AM

@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.

This revision was automatically updated to reflect the committed changes.