-
Notifications
You must be signed in to change notification settings - Fork 13.2k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
BTreeMap/Set don't have debug visualizers #90520
Comments
@rustbot claim |
@rustbot release-assignment Going to relinquish this, it's more complex than I have time for right now. For anyone who wants to pick this up, it will take translating this algorithm into this NatVis file. Tests should be added here. |
@rustbot claim |
@rustbot release-assignment |
@rustbot claim |
This is a tough one to tackle. The objective is simple: Perform a preorder walk across an N-ary tree, trivially expressed as a recursive algorithm. The crux of the matter lies in the incompatibility of properties of the participants:
To save anyone trying to get involved the time to rediscover the same issues, I'm leaving a few notes here: The Obvious SolutionIdeally, the visualizer would be a simple application of recursion as implemented in the following .natvis: <?xml version="1.0" encoding="utf-8"?>
<AutoVisualizer xmlns="http://schemas.microsoft.com/vstudio/debugger/natvis/2010">
<!-- BTreeMap<K, V, A> -->
<Type Name="alloc::collections::btree::map::BTreeMap<*, *, *>">
<Intrinsic Name="root_node" Expression="root.variant1.value.__0.node.pointer"/>
<Intrinsic Name="is_empty" Expression="root_node()->len == 0"/>
<DisplayString>{{ size={length} }}</DisplayString>
<Expand>
<!-- Expand root node unless empty -->
<ExpandedItem Condition="!is_empty()">root_node()</ExpandedItem>
</Expand>
</Type>
<!-- InternalNode<K, V> -->
<Type Name="alloc::collections::btree::node::InternalNode<*, *>">
<Expand>
<!-- Expand left child -->
<ExpandedItem>edges[0]</ExpandedItem>
<CustomListItems>
<Variable Name="idx" InitialValue="0"/>
<Loop Condition="idx < len">
<!-- Add current item -->
<Item Name="{data->keys[idx].value}">data->vals[idx].value</Item>
<Exec>++idx</Exec>
<!-- Expand right child (if only this was supported) -->
<ExpandedItem>edges[idx]</ExpandedItem>
</Loop>
</CustomListItems>
</Expand>
</Type>
<!-- LeafNode<K, V> -->
<Type Name="alloc::collections::btree::node::LeafNode<*, *>">
<Expand>
<CustomListItems>
<Variable Name="idx" InitialValue="0"/>
<Loop Condition="idx < len">
<Item Name="{keys[idx].value}">vals[idx].value</Item>
<Exec>++idx</Exec>
</Loop>
</CustomListItems>
</Expand>
</Type>
</AutoVisualizer> This won't work, however, for two reasons:
The second issue eventually made me give up on the idea of solving this using recursion. To explain the unsolvable challenges more easily (as I currently understand), let me quickly outline the core Decrusting the
|
Part 2 of <N>My previous submission left off with two unsolved riddles:
As I discovered, the latter has an obvious solution once you understand the issue. The hard part was allowing myself the liberty1 to question the accuracy of the NatVis diagnostic. Naming (generic) typesFor reference, here's the abridged version:
This is hideously misleading.
(InternalNode<$T1,$T2>*)ptr which expands to The fix is simple: Replacing (InternalNode<$T1,$T2>*)ptr with (InternalNode<$T1,$T2 >*)ptr turns the
This was frustratingly difficult and time-consuming to discover. Anyway, with the roadblock gone, we can finally move ahead. Outsourcing the StackThis one took me a while to see through. A recursion can be turned into an iteration so long as we have access to a stack for backtracking. Since the NatVis framework doesn't provide a stack-like data structure I then set out to find a solution that doesn't involve a stack. Little did I know that the problem statement was all wrong until I found this Stack Overflow answer that put it right in front of me:
The
This finally looks like something that could be expressed under the constraints of the NatVis framework. "Gentlemen, Start Your Engines!"The following is the first iteration that occasionally doesn't fail, as long as you hold it just the right way. Proceed at your own peril, with extreme caution. The overall design is based on implementing the core of the visualizer under the The entire set of state information required for traversal consists of the following:
This should help you find your way around the implementation: <?xml version="1.0" encoding="utf-8"?>
<AutoVisualizer xmlns="http://schemas.microsoft.com/vstudio/debugger/natvis/2010">
<!-- BTreeMap<K, V, A> -->
<Type Name="alloc::collections::btree::map::BTreeMap<*, *, * >">
<Intrinsic Name="is_empty" Expression="length == 0"/>
<DisplayString>{{ size={length} }}</DisplayString>
<Expand>
<Item Name="[size]" ExcludeView="simple">length</Item>
<!-- Expand root node unless empty -->
<ExpandedItem Condition="!is_empty()">root.variant1.value.__0</ExpandedItem>
</Expand>
</Type>
<!-- BTreeSet<T, A> -->
<Type Name="alloc::collections::btree::set::BTreeSet<*, * >">
<Intrinsic Name="is_empty" Expression="map.length == 0"/>
<DisplayString>{{ size={map.length} }}</DisplayString>
<Expand>
<Item Name="[size]" ExcludeView="simple">map.length</Item>
<!-- Expand map's root node unless empty -->
<ExpandedItem Condition="!is_empty()">map.root.variant1.value.__0</ExpandedItem>
</Expand>
</Type>
<!-- NodeRef<BorrowType, K, V, Type> -->
<Type Name="alloc::collections::btree::node::NodeRef<*, *, *, *>">
<Intrinsic Name="cast_to_internal"
Expression="(::alloc::collections::btree::node::InternalNode<$T2,$T3 >*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_leaf"
Expression="(::alloc::collections::btree::node::LeafNode<$T2,$T3 >*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<DisplayString>{{ height={height} }}</DisplayString>
<Expand>
<CustomListItems>
<Variable Name="depth" InitialValue="0"/>
<Variable Name="curr" InitialValue="node.pointer"/>
<Variable Name="curr_idx" InitialValue="-1"/>
<Loop Condition="curr != 0">
<!-- Leaf node -->
<If Condition="depth == height">
<!-- Add items -->
<Exec>curr_idx = 0</Exec>
<Loop Condition="curr_idx < curr->len">
<Item Name="{curr->keys[curr_idx].value}">curr->vals[curr_idx].value</Item>
<Exec>++curr_idx</Exec>
</Loop>
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
<Break Condition="curr == 0"/>
</If>
<!-- Internal node -->
<Else>
<!--
All items of the current node have been handled (i.e., we've just moved up
from the right-most edge)
-->
<If Condition="curr_idx >= curr->len">
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
<Break Condition="curr == 0"/>
</If>
<!--
No items have been visited in this node (i.e., we've just moved down)
-->
<Elseif Condition="curr_idx < 0">
<!-- Move down -->
<Exec>++depth</Exec>
<Exec>curr = cast_to_internal(curr)->edges[0].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</Elseif>
<!--
We're currently expanding this internal node: Add the current item and move
to the next (right) child
-->
<Else>
<!-- Add current item -->
<Item Name="{curr->keys[curr_idx].value}">curr->vals[curr_idx].value</Item>
<!-- Move to next child -->
<Exec>++depth</Exec>
<Exec>++curr_idx</Exec>
<Exec>curr = cast_to_internal(curr)->edges[curr_idx].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</Else>
</Else>
</Loop>
</CustomListItems>
</Expand>
</Type>
<!-- NodeRef<BorrowType, K, (), Type> -->
<Type Name="alloc::collections::btree::node::NodeRef<*, *, alloc::collections::btree::set_val::SetValZST, *>">
<Intrinsic Name="cast_to_internal"
Expression="(::alloc::collections::btree::node::InternalNode<$T2,alloc::collections::btree::set_val::SetValZST>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_leaf"
Expression="(::alloc::collections::btree::node::LeafNode<$T2,alloc::collections::btree::set_val::SetValZST>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<DisplayString>{{ moose={height} }}</DisplayString>
<Expand>
<CustomListItems>
<Variable Name="depth" InitialValue="0"/>
<Variable Name="curr" InitialValue="node.pointer"/>
<Variable Name="curr_idx" InitialValue="-1"/>
<Variable Name="element_idx" InitialValue="0"/>
<Loop Condition="curr != 0">
<!-- Leaf node -->
<If Condition="depth == height">
<!-- Add items -->
<Exec>curr_idx = 0</Exec>
<Loop Condition="curr_idx < curr->len">
<Item Name="[{element_idx}]">curr->keys[curr_idx].value</Item>
<Exec>++element_idx</Exec>
<Exec>++curr_idx</Exec>
</Loop>
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
<Break Condition="curr == 0"/>
</If>
<!-- Internal node -->
<Else>
<!--
All items of the current node have been handled (i.e., we've just moved up
from the right-most edge)
-->
<If Condition="curr_idx >= curr->len">
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
<Break Condition="curr == 0"/>
</If>
<!--
No items have been visited in this node (i.e., we've just moved down)
-->
<Elseif Condition="curr_idx < 0">
<!-- Move down -->
<Exec>++depth</Exec>
<Exec>curr = cast_to_internal(curr)->edges[0].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</Elseif>
<!--
We're currently expanding this internal node: Add the current item and move
to the next (right) child
-->
<Else>
<!-- Add current item -->
<Item Name="[{element_idx}]">curr->keys[curr_idx].value</Item>
<Exec>++element_idx</Exec>
<!-- Move to next child -->
<Exec>++depth</Exec>
<Exec>++curr_idx</Exec>
<Exec>curr = cast_to_internal(curr)->edges[curr_idx].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</Else>
</Else>
</Loop>
</CustomListItems>
</Expand>
</Type>
</AutoVisualizer> I'd love to get feedback on this across different debuggers and Notable FatalitiesFeeding the markup above into a debugger has the intended effect, provided that we're not feeding it into the wrong debugger, or having the debugger look at a Presented with the test code from my previous comment that instantiates a
In summary: Out of the three distinct debuggers tested, each one is in mutual disagreement with each other over identical input4. This is a really bad spot to be in. I'll look some more into addressing this at some point. Moving ahead from a dire state, now, can it get any worse? Why, sure, thanks for your continued interest! All it takes to break the happy path (VS2022) is this innocuous-looking Rust code: let mut numbers = BTreeMap::new();
for i in 0..12 {
numbers.insert(i, format!("{i}"));
}
println!("{numbers:?}"); It constructs a The specific error is in the I have a rough idea of how to work around this, but haven't gotten to it yet. Wrapping UpThis is a substantial step forward, but the implementation is still very much experimental. In addition to the known issues, I'm sure there are more to be discovered. Your feedback is much appreciated. Footnotes
|
Part 3 of <N>Quick update (trust me) on the issue that prevented the visualizer from handling The issue revolved around the unanswerable question of whether the <!-- NodeRef<BorrowType, K, V, Type> -->
<Type Name="alloc::collections::btree::node::NodeRef<*, *, *, *>">
<Intrinsic Name="cast_to_internal"
Optional="true"
Expression="(::alloc::collections::btree::node::InternalNode<$T2,$T3 >*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_internal"
Expression="(::alloc::collections::btree::node::InternalNode<$T2,$T3>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_leaf"
Optional="true"
Expression="(::alloc::collections::btree::node::LeafNode<$T2,$T3 >*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_leaf"
Expression="(::alloc::collections::btree::node::LeafNode<$T2,$T3>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<!-- ... -->
</Type> The The implementation under The next step is figuring out the WinDbg failures. |
Part 4 of <N>The previous fix to the That's far from ideal, but at least it's no longer terrible, so I went ahead to see what CDB1 makes of this. The good news is that things didn't get worse: CDB behaves like either of the WinDbg debuggers. With the debuggers failing to evaluate the visualizers offering no diagnostics2 addressing the issue becomes a game of trial-and-error. Here's what I tried so far:
None of these had any observable effect on WinDbg (classic), WinDbg (formerly Preview), or CDB. While I'm not completely out of ideas just yet, randomly trying things doesn't feel like an incredibly efficient use of my time. If anyone has any suggestions on how to diagnose NatVis errors with those debuggers please do share them. For reference, here's the current iteration of the visualizer. It's slightly shorter, but not by much. <?xml version="1.0" encoding="utf-8"?>
<AutoVisualizer xmlns="http://schemas.microsoft.com/vstudio/debugger/natvis/2010">
<!-- BTreeMap<K, V, A> -->
<Type Name="alloc::collections::btree::map::BTreeMap<*, *, * >">
<Intrinsic Name="is_empty" Expression="length == 0"/>
<DisplayString>{{ size={length} }}</DisplayString>
<Expand>
<Item Name="[size]" ExcludeView="simple">length</Item>
<!-- Expand root node unless empty -->
<ExpandedItem Condition="!is_empty()">root.variant1.value.__0</ExpandedItem>
</Expand>
</Type>
<!-- BTreeSet<T, A> -->
<Type Name="alloc::collections::btree::set::BTreeSet<*, * >">
<Intrinsic Name="is_empty" Expression="map.length == 0"/>
<DisplayString>{{ size={map.length} }}</DisplayString>
<Expand>
<Item Name="[size]" ExcludeView="simple">map.length</Item>
<!-- Expand map's root node unless empty -->
<ExpandedItem Condition="!is_empty()">map.root.variant1.value.__0</ExpandedItem>
</Expand>
</Type>
<!-- NodeRef<BorrowType, K, V, Type> -->
<Type Name="alloc::collections::btree::node::NodeRef<*, *, *, *>">
<Intrinsic Name="cast_to_internal"
Optional="true"
Expression="(::alloc::collections::btree::node::InternalNode<$T2,$T3 >*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_internal"
Expression="(::alloc::collections::btree::node::InternalNode<$T2,$T3>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_leaf"
Optional="true"
Expression="(::alloc::collections::btree::node::LeafNode<$T2,$T3 >*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_leaf"
Expression="(::alloc::collections::btree::node::LeafNode<$T2,$T3>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<DisplayString>{{ height={height} }}</DisplayString>
<Expand>
<CustomListItems>
<Variable Name="depth" InitialValue="0"/>
<Variable Name="curr" InitialValue="node.pointer"/>
<Variable Name="curr_idx" InitialValue="-1"/>
<Loop Condition="curr != 0">
<!-- Leaf node -->
<If Condition="depth == height">
<!-- Add items -->
<Exec>curr_idx = 0</Exec>
<Loop Condition="curr_idx < curr->len">
<Item Name="{curr->keys[curr_idx].value}">curr->vals[curr_idx].value</Item>
<Exec>++curr_idx</Exec>
</Loop>
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
</If>
<!-- Internal node -->
<Else>
<!-- First visit -->
<If Condition="curr_idx < 0">
<!-- Move down to the left child -->
<Exec>++depth</Exec>
<Exec>curr = cast_to_internal(curr)->edges[0].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</If>
<!-- nth visit (n < len) -->
<Elseif Condition="curr_idx < curr->len">
<!-- Add current item -->
<Item Name="{curr->keys[curr_idx].value}">curr->vals[curr_idx].value</Item>
<!-- Move down to right child -->
<Exec>++depth</Exec>
<Exec>curr = cast_to_internal(curr)->edges[curr_idx + 1].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</Elseif>
<!-- All items visited -->
<Else>
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
</Else>
</Else>
</Loop>
</CustomListItems>
</Expand>
</Type>
<!-- NodeRef<BorrowType, K, (), Type> -->
<Type Name="alloc::collections::btree::node::NodeRef<*, *, alloc::collections::btree::set_val::SetValZST, *>">
<Intrinsic Name="cast_to_internal"
Expression="(::alloc::collections::btree::node::InternalNode<$T2,alloc::collections::btree::set_val::SetValZST>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_leaf"
Expression="(::alloc::collections::btree::node::LeafNode<$T2,alloc::collections::btree::set_val::SetValZST>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<DisplayString>{{ height={height} }}</DisplayString>
<Expand>
<CustomListItems>
<Variable Name="depth" InitialValue="0"/>
<Variable Name="curr" InitialValue="node.pointer"/>
<Variable Name="curr_idx" InitialValue="-1"/>
<Variable Name="element_idx" InitialValue="0"/>
<Loop Condition="curr != 0">
<!-- Leaf node -->
<If Condition="depth == height">
<!-- Add items -->
<Exec>curr_idx = 0</Exec>
<Loop Condition="curr_idx < curr->len">
<Item Name="[{element_idx}]">curr->keys[curr_idx].value</Item>
<Exec>++element_idx</Exec>
<Exec>++curr_idx</Exec>
</Loop>
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
</If>
<!-- Internal node -->
<Else>
<!-- First visit -->
<If Condition="curr_idx < 0">
<!-- Move down to the left child -->
<Exec>++depth</Exec>
<Exec>curr = cast_to_internal(curr)->edges[0].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</If>
<!-- nth visit (n < len) -->
<Elseif Condition="curr_idx < curr->len">
<!-- Add current item -->
<Item Name="[{element_idx}]">curr->keys[curr_idx].value</Item>
<Exec>++element_idx</Exec>
<!-- Move down to right child -->
<Exec>++depth</Exec>
<Exec>curr = cast_to_internal(curr)->edges[curr_idx + 1].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</Elseif>
<!-- All items visited -->
<Else>
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
</Else>
</Else>
</Loop>
</CustomListItems>
</Expand>
</Type>
</AutoVisualizer> This works in Visual Studio 2022 for Footnotes |
Part 5 of <N>This is a mixed update, with progress and setbacks. The WinDbg/CDB NatVis evaluation errors were (in part) down to the type naming rules spelled out in part 2 being incorrect. Here is the corrected version:
Applying the revised rules fixes the The I don't know how to approach this. Suggestions welcome. Keeping with the tradition, here's the current iteration of the visualizer: <?xml version="1.0" encoding="utf-8"?>
<AutoVisualizer xmlns="http://schemas.microsoft.com/vstudio/debugger/natvis/2010">
<!-- BTreeMap<K, V, A> -->
<Type Name="alloc::collections::btree::map::BTreeMap<*, *, *>">
<Intrinsic Name="is_empty" Expression="length == 0"/>
<DisplayString>{{ size={length} }}</DisplayString>
<Expand>
<Item Name="[size]" ExcludeView="simple">length</Item>
<!-- Expand root node unless empty -->
<ExpandedItem Condition="!is_empty()">root.variant1.value.__0</ExpandedItem>
</Expand>
</Type>
<!-- BTreeSet<T, A> -->
<Type Name="alloc::collections::btree::set::BTreeSet<*, * >">
<Intrinsic Name="is_empty" Expression="map.length == 0"/>
<DisplayString>{{ size={map.length} }}</DisplayString>
<Expand>
<Item Name="[size]" ExcludeView="simple">map.length</Item>
<!-- Expand map's root node unless empty -->
<ExpandedItem Condition="!is_empty()">map.root.variant1.value.__0</ExpandedItem>
</Expand>
</Type>
<!-- NodeRef<BorrowType, K, V, Type> -->
<Type Name="alloc::collections::btree::node::NodeRef<*, *, *, *>">
<Intrinsic Name="cast_to_internal"
Optional="true"
Expression="(alloc::collections::btree::node::InternalNode<$T2,$T3 >*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_internal"
Expression="(alloc::collections::btree::node::InternalNode<$T2,$T3>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_leaf"
Optional="true"
Expression="(alloc::collections::btree::node::LeafNode<$T2,$T3 >*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_leaf"
Expression="(alloc::collections::btree::node::LeafNode<$T2,$T3>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<DisplayString>{{ height={height} }}</DisplayString>
<Expand>
<CustomListItems>
<Variable Name="depth" InitialValue="0"/>
<Variable Name="curr" InitialValue="node.pointer"/>
<Variable Name="curr_idx" InitialValue="-1"/>
<Loop Condition="curr != 0">
<!-- Leaf node -->
<If Condition="depth == height">
<!-- Add items -->
<Exec>curr_idx = 0</Exec>
<Loop Condition="curr_idx < curr->len">
<Item Name="{curr->keys[curr_idx].value}">curr->vals[curr_idx].value</Item>
<Exec>++curr_idx</Exec>
</Loop>
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
</If>
<!-- Internal node -->
<Else>
<!-- First visit -->
<If Condition="curr_idx < 0">
<!-- Move down to the left child -->
<Exec>++depth</Exec>
<Exec>curr = cast_to_internal(curr)->edges[0].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</If>
<!-- nth visit (n < len) -->
<Elseif Condition="curr_idx < curr->len">
<!-- Add current item -->
<Item Name="{curr->keys[curr_idx].value}">curr->vals[curr_idx].value</Item>
<!-- Move down to right child -->
<Exec>++depth</Exec>
<Exec>curr = cast_to_internal(curr)->edges[curr_idx + 1].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</Elseif>
<!-- All items visited -->
<Else>
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
</Else>
</Else>
</Loop>
</CustomListItems>
</Expand>
</Type>
<!-- NodeRef<BorrowType, K, (), Type> -->
<Type Name="alloc::collections::btree::node::NodeRef<*, *, alloc::collections::btree::set_val::SetValZST, *>">
<Intrinsic Name="cast_to_internal"
Expression="(alloc::collections::btree::node::InternalNode<$T2,alloc::collections::btree::set_val::SetValZST>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<Intrinsic Name="cast_to_leaf"
Expression="(alloc::collections::btree::node::LeafNode<$T2,alloc::collections::btree::set_val::SetValZST>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
<DisplayString>{{ height={height} }}</DisplayString>
<Expand>
<CustomListItems>
<Variable Name="depth" InitialValue="0"/>
<Variable Name="curr" InitialValue="node.pointer"/>
<Variable Name="curr_idx" InitialValue="-1"/>
<Variable Name="element_idx" InitialValue="0"/>
<Loop Condition="curr != 0">
<!-- Leaf node -->
<If Condition="depth == height">
<!-- Add items -->
<Exec>curr_idx = 0</Exec>
<Loop Condition="curr_idx < curr->len">
<Item Name="[{element_idx}]">curr->keys[curr_idx].value</Item>
<Exec>++element_idx</Exec>
<Exec>++curr_idx</Exec>
</Loop>
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
</If>
<!-- Internal node -->
<Else>
<!-- First visit -->
<If Condition="curr_idx < 0">
<!-- Move down to the left child -->
<Exec>++depth</Exec>
<Exec>curr = cast_to_internal(curr)->edges[0].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</If>
<!-- nth visit (n < len) -->
<Elseif Condition="curr_idx < curr->len">
<!-- Add current item -->
<Item Name="[{element_idx}]">curr->keys[curr_idx].value</Item>
<Exec>++element_idx</Exec>
<!-- Move down to right child -->
<Exec>++depth</Exec>
<Exec>curr = cast_to_internal(curr)->edges[curr_idx + 1].value.value.pointer</Exec>
<Exec>curr_idx = -1</Exec>
</Elseif>
<!-- All items visited -->
<Else>
<!-- Move up -->
<Exec>--depth</Exec>
<Exec>curr_idx = curr->parent_idx.value.value</Exec>
<Exec>curr = cast_to_leaf(curr->parent.variant1.value.__0.pointer)</Exec>
</Else>
</Else>
</Loop>
</CustomListItems>
</Expand>
</Type>
</AutoVisualizer> |
Part 6 of <N>The last part left off with the insight that "overloading" It was the only idea I came up with to have the debuggers' EE's dispatch to different implementations based on properties of a type. With that option gone, the decision-making has to be expressed in .natvis markup. Natvis has very little support to work with types, so the immediate challenge is to turn this type puzzle into something that Natvis can express. Figuring out whether a type is generic can be turned into a two-step string problem1:
The first step has a surprisingly obvious solution: Generic type parameters can be referenced via the Attempting to implement step two is when debuggers start showing divergent behavior: In lieu of a Debugger support, however, diverges when attempting to index into the character string. The following intrinsic implements the required functionality: <!-- "$T2" [strlen( "$T2" ) - 1] == '>' -->
<Intrinsic Name="is_generic"
Expression=""$T2"[strlen("$T2") - 1] == '>'"/> It works fine in Visual Studio but fails to evaluate in WinDbg and CDB. I narrowed down the issue to the latter debuggers' inability to index into character strings via subscript notation. Using pointer-arithmetic instead turns this into a chicken-and-egg problem: Finding the pointer to the first character requires subscript notation, i.e., At this point, I have run out of creativity. There's nothing left I could think of to solve this issue. It is unfortunate to have to let go with just one final issue left to address. I'm still holding high hopes that this turns out to be a skill issue, and I'm leaving this for someone smarter than me to pick up in the future. Speaking of which, @michaelwoerister has frequently responded to Natvis-related issues. Are you that person (or know of someone who is)? Footnotes
|
It would be nice if BTreeSet and BTreeMap had visualizers. These seem to be in
.natvis
files for otherstd
collections, but the BTree structures seem to have been overlooked.As it is now, debugging these structures is extremely unwieldy. See screenshot:

originally reported here https://internals.rust-lang.org/t/feature-request-debug-visualizer-for-btreemap-set/15543
The text was updated successfully, but these errors were encountered: