Open rotu opened 2 years ago
@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:
BTreeMap
)To save anyone trying to get involved the time to rediscover the same issues, I'm leaving a few notes here:
Ideally, 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:
<ExpandedItem>
cannot appear under a <Loop>
context. Commenting out that line makes the document valid and the visualizer starts working (for BTreeMap
s of length 11 or less anyway).BTreeMap
are statically typed as pointers to LeafNode
s, invalidating the debugger's ability to dispatch to different visualizer code based on type.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 BTreeMap
structure.
BTreeMap
BTreeMap
is an implementation of the B-tree data structure. It is a surprisingly simple data structure with much of its simplicity lost to the realities of implementing a self-referential data structure in Rust. The following is an attempt at capturing the essentials[^1].
A flattened-out approximation of the BTreeMap
structure roughly looks like this:
struct BTreeMap<K, V> {
root: *const LeafNode<K, V>,
length: usize,
height: usize,
}
This is a simplified version that, while different, doesn't deviate from the actual implementation in a meaningful way. It stores a pointer to the tree root (unless empty) and the tree height
. The overall length
is kept alongside as an optimization only.
The LeafNode
type encompasses the majority of the data. It doesn't need much simplification:
struct LeafNode<K, V> {
parent: *const InternalNode<K, V>,
parent_idx: MaybeUninit<u16>,
len: u16,
keys: [MaybeUninit<K>; CAPACITY],
vals: [MaybeUninit<V>; CAPACITY],
}
Each node (except for the root node) stores a pointer to its parent
and a parent_idx
that designates the position of this node in the parent's edges
array. The len
field describes the number of valid keys
and vals
.
The final piece is the InternalNode
:
#[repr(C)]
struct InternalNode<K, V> {
data: LeafNode<K, V>,
edges: [*const LeafNode<K, V>; CAPACITY + 1],
}
This is a LeafNode
with an edges
array appended, that stores pointers to children to the left and right of each element in data
. The #[repr(C)]
attribute prevents field reordering, making InternalNode
binary layout compatible with LeafNode
. This is in preparation for what is effectively a hand-rolled version of run-time polymorphism.
Internally, the implementation constructs InternalNode
s and LeafNode
s as required, but will always refer to them through pointers to LeafNode
s. The concrete type of a node is recovered at run-time based on its distance[^2] from the root. Since a B-tree is balanced, all leaf nodes appear on the same level. This level is described by the tree's height
.
The information above produces a crucial insight: All nodes in a BTreeMap
tree are type-erased. For any given node, its type has to be recovered at run-time and a visualizer alike. The type is a function of the node's distance from the root and the tree's height.
While it is easy[^3] to calculate the distance of a node by following the chain of parent
pointers, the tree's height
isn't reachable from any node. It is stored in the BTreeMap
(technically, in a NodeRef
, but that isn't reachable from any node either).
Determination of a node's specific type requires external context. I'm not aware of a way to pass context between different visualizers (or even the same visualizer), making this approach unfeasible. So...
Knowing the tree's height
is required to make up for the missing type information. While there is no way to pass information across visualizers it looks like the entirety of the visualizer needs to be implemented on a type where this information is reachable, i.e., BTreeMap
or NodeRef
.
A corollary of this is that the tree walk needs to be implemented as an iteration. Raymond Chen has written a compact outline of the algorithm in his article Tree-walking algorithms: Incrementally performing a preorder walk of an N-ary tree. It feels like this can be represented by a DFA that operates in finite space, both are requirements of the NatVis framework.
This is the approach I'm (planning on) evaluating, but I'm stuck on a more fundamental issue: Naming types. Regardless of implementation, at some point, a cast from a LeafNode
pointer to an InternalNode
pointer is required. That's what the following intrinsic tries to do:
<Intrinsic Name="cast_to_internal"
Expression="(::alloc::collections::btree::node::InternalNode<$T1, $T2>*)ptr">
<Parameter Name="ptr" Type="void*"/>
</Intrinsic>
This is met with the following diagnostic:
Natvis: [...]: Error: identifier "alloc::collections::btree::node" is undefined
Error while evaluating '(::alloc::collections::btree::node::InternalNode<ref$<str$>, ref$<str$> >*)ptr' in the context of type 'btreemap_natvis.exe!alloc::collections::btree::map::BTreeMap<ref$<str$>,ref$<str$>,alloc::alloc::Global>'.
I feel like I've hit a brick wall here. Just to make sure this wasn't down to me fumbling the generic parameters or namespace lookup I replaced the Expression
with (BTreeMap*)ptr
. That, however, produced an equivalent diagnostic. I honestly don't know where to go from here, so any feedback is much appreciated.
Thankfully, this is a rabbit hole, and hitting two dead ends doesn't mean there weren't others to discover.
As established above, application of recursion hinges upon the ability to recover type information locally, which—in turn—requires maintaining state across or within visualizers. I would have let go if it wasn't for the documentation entry on debugger intrinsic functions. The "Miscellaneous" section lists three that are of particular interest:
TreeTraverse_Init()
: Initializes a new tree traversal.TreeTraverse_Next()
: Retrieves nodes from a pending tree traversal.TreeTraverse_Skip()
: Skips nodes in a pending tree traversal.These used to be documented with parameters and return values that read like they could solve the primary issue here. In response to a (now deleted) issue, however, the documentation was changed to read that those functions are intended to be used with extension-based (VSIX) visualizers.
This never made sense to me: VSIX visualizers are binaries that can execute arbitrary code. I did respond to the issue linked just above to ask for clarification, but that conversation is lost to history. I meant to revive the issue only to find that the repository is no longer accepting public feedback via issues.
Any sort of information on those intrinsics would be incredibly valuable.
Debugging the debugger is always a challenge. I'd been using the following setup to quickly iterate on ideas:
Code
The following serves as a convenient debugging target:
pub use std::collections::BTreeMap;
#[debugger_visualizer(natvis_file = "../btreemap_natvis.natvis")]
mod dummy {}
fn main() {
let mut movie_reviews = BTreeMap::new();
// insert 11 items to fill the root node
movie_reviews.insert("Office Space", "Deals with real issues in the workplace.");
movie_reviews.insert("Pulp Fiction", "Masterpiece.");
movie_reviews.insert("The Godfather", "Very enjoyable.");
movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");
movie_reviews.insert("A", "value");
movie_reviews.insert("B", "value");
movie_reviews.insert("C", "value");
movie_reviews.insert("D", "value");
movie_reviews.insert("E", "value");
movie_reviews.insert("F", "value");
movie_reviews.insert("G", "value");
// insert 12th item to turn this into a tree
movie_reviews.insert("H", "value");
println!("{movie_reviews:?}");
}
This can be compiled into a binary ready for debugging. The #[debugger_visualizer]
attribute conveniently dumps the natvis_file
into the PDB so it doesn't have to be manually loaded into the debugger later. Switching between different implementations is as simple as replacing the file name followed by a cargo build
.
Debugging
I'm using Visual Studio Community 2022 for evaluation. It's one of the few Windows debuggers that can be configured to produce NatVis diagnostics[^4]. Sadly, this is as much debugging support as I'm aware of.
Setting up Visual Studio to debug a Rust executable is easy, but not entirely obvious so I'm including the instructions here:
File
| Open
and select Project/Solution...
Open
(make sure the filter in the bottom right is set to "All Project File"). This creates a temporary, in-memory .sln file with sufficient information to launch a debugging session.File
| Open
and select File...
This worked sufficiently well for me, although there is the occasional hiccup where Visual Studio's debugger will claim the PDB refers to a different version of the source (often when exchanging .natvis files). This is easily resolved by a cargo clean
and cargo build
.
That's all I have to share. Hopefully, some of the information is useful enough to reboot the conversation and move this old issue closer to completion.
[^1]: You'll find the full, unadorned details here: Rust Collections Case Study: BTreeMap.
[^2]: The distance of a node from the root is the number of edges
followed to reach it. This is equivalent to the number of parent
pointers followed to reach the root node.
[^3]: Not trivially easy, though, since <Intrinsic>
s do not support recursive evaluation. This still requires a <Loop>
of sorts.
[^4]: Apparently, this is also possible with a Visual Studio Code extension but I have no experience with that.
My previous submission left off with two unsolved riddles:
TreeTraverse_*
intrinsics?As I discovered, the latter has an obvious solution once you understand the issue. The hard part was allowing myself the liberty[^1] to question the accuracy of the NatVis diagnostic.
For reference, here's the abridged version:
Error while evaluating '(InternalNode<ref$<str$>, ref$<str$> >*)ptr' [...]
This is hideously misleading.
(InternalNode<ref$<str$>, ref$<str$> >*)ptr
isn't actually what the Expression Evaluator (EE) was trying to resolve. It was going off of
(InternalNode<$T1,$T2>*)ptr
which expands to (InternalNode<ref$<str$>,ref$<str$>>*)ptr
. Modulo whitespace, this looks exactly like the expression in the diagnostic. Except, one of those whitespaces is meaningful, a corollary of the fact that >>
is ambiguous in C++. C++11 allows compilers some leeway in disambiguating >>
but EE's aren't full-blown C++ compiler frontends.
The fix is simple: Replacing
(InternalNode<$T1,$T2>*)ptr
with
(InternalNode<$T1,$T2 >*)ptr
turns the <Intrinsic>
valid. There are a few more quirks surrounding type names that I ran into, and I'm sure others will, too. Here is a list of my findings:
::
::
),core
(e.g., core::ptr
and ::core::ptr
can be used interchangeably; I haven't investigated what's behind this inconsistency)>
) must be prefixed by exactly one whitespace
>
(I'll have to come back to this later...),<Type Name="...">
match pattern (these appear to be surprisingly whitespace-insensitive)This was frustratingly difficult and time-consuming to discover. Anyway, with the roadblock gone, we can finally move ahead.
This 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:
You don't need a stack, since the tree itself already is (or contains) all the stack you need.
The BTreeMap
implementation is indeed sufficient to use a variation[^3] of Morris Traversal, an iterative tree-walking algorithm that doesn't rely on a separate stack:
curr
with the root
nodecurr
isn't null
curr
is a leaf node, print all items and set curr = curr.parent
curr
, continue down the left edge: curr = curr.edges[0]
nth
time visiting curr
, where n < curr.len
, print the nth
item, and move to the right child: curr = curr.edges[n + 1]
curr = curr.parent
This finally looks like something that could be expressed under the constraints of the NatVis framework.
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 NodeRef
type, with BTreeMap
and BTreeSet
delegating item expansion. There are two almost identical implementations: One for the generic NodeRef<*, *, *, *>
type pattern in addition to the NodeRef<*, *, SetValZST, *>
"specialization". The latter handles the BTreeSet
case.
The entire set of state information required for traversal consists of the following:
depth
: The distance from the root node; required to tell internal and leaf nodes apart.curr
: Pointer to the node currently being expanded.curr_idx
: Item index into the node currently being expanded; set to -1
on first visit.SetValZST
only] element_idx
: Cumulative item counter; used for [index]: key
visualization in the BTreeSet
case.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 BTreeMap
/BTreeSet
instantiations, but I need to reiterate: Tread carefully. Don't leave any unsaved work behind. The introductory warning wasn't just hyperbole.
Feeding 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 BTreeMap
instantiation where V
is too boring (yet not quite as boring as a SetValZST
). Failing that the script will have some effect.
Presented with the test code from my previous comment that instantiates a BTreeMap<&str, &str>
(&str
is represented as ref$<str$>
in the debug symbol database), here's how debuggers responded:
[RawView]
instead?"dx
a non-empty subject. There's a 0xC0000005
in the application event log as if it was about to start cussing at me.In summary: Out of the three distinct debuggers tested, each one is in mutual disagreement with each other over identical input[^4]. 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 BTreeMap
, just like before, but uses a "boring" String
for its V
type argument. This enters the "unless the preceding symbol ends in anything other than a >
" clause under the Naming (generic) types section above.
The specific error is in the cast_to_[internal|leaf]
intrinsics, which made very sure to prefix the >
(>
) with exactly one whitespace. But now the preceding symbol is String
, which doesn't end in >
, meaning that the deliberate whitespace causes a type-lookup failure.
I have a rough idea of how to work around this, but haven't gotten to it yet.
This 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.
[^1]: Rafael did the grunt work and created Rust bindings for the DIA SDK, that let me quickly put together a tool to dump the (unperturbed) SymTagUDT
table entries from a PDB.
[^2]: See part 5 for corrections.
[^3]: I'm not sure this is accurate. I'd be happy to learn if someone knows what algorithm this is.
[^4]: It feels like the WinDbg (variants') EE's fail due to different implementations of (implicit) integral type promotions/conversions. Researching this is on my TODO list.
Quick update (trust me) on the issue that prevented the visualizer from handling BTreeMap<i32, String>
: The NatVis schema allows specifying elements multiple times. When the EE sees multiple alternatives it tries to evaluate them in order until it finds one that doesn't fail (the moral equivalent of SFINAE in C++).
The issue revolved around the unanswerable question of whether the V
type argument ends in a >
character. The solution is thus to provide two versions of the cast_to_*
intrinsics to cover either case and have the EE figure out which one to use:
<!-- 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 Optional="true"
attribute isn't functionally required. It just keeps the noise level in the NatVis diagnostics log down for expected evaluation errors.
The implementation under NodeRef<BorrowType, K, (), Type>
doesn't need this special treatment since we know the (problematic) type ahead of time.
The next step is figuring out the WinDbg failures.
The previous fix to the cast_to_*
intrinsics magically resolved the issue of WinDbg (classic) crashing. With that in place WinDbg (classic) and WinDbg (formerly Preview) exhibit identical behavior: The visualizer produces the intended output for "trees" up to (and including) 11 elements, but stops being evaluated the moment a subsequently added element splits the root node.
That's far from ideal, but at least it's no longer terrible, so I went ahead to see what CDB[^1] 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 diagnostics[^2] addressing the issue becomes a game of trial-and-error. Here's what I tried so far:
(__int64)
to prevent any signed
/unsigned
mismatches.<Elseif>
sequence with nested <If>
/<Else>
expressions.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 BTreeSet
and BTreeMap
with generic and non-generic types of V
, even though it hasn't seen extensive testing.
[^1]: Supporting CDB is crucially important for automated testing. [^2]: I dumped a list of all installed ETW trace providers but nothing looked immediately applicable.
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:
::
>
) must be prefixed by exactly one whitespace
>
,<Type Name="...">
match pattern (these appear to be surprisingly whitespace-insensitive)Applying the revised rules fixes the BTreeSet
portion of the visualizer for WinDbg (classic), WinDbg (formerly Preview), and CDB. This is a substantial step forward. However, there's still an issue that prevents these debuggers from visualizing BTreeMap
s:
The cast_to_*
intrinsics need to name the target type. Since that is a generic type the final >
needs to be conditionally prefixed by a whitespace. The solution to "overload" the intrinsics and rely on SFINAE-pruning to reject the incorrect version works in Visual Studio 2022 but not in WinDbg/CDB.
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>
The last part left off with the insight that "overloading" <Intrinsic>
s doesn't work in WinDbg/CDB. This was the initial attempt at conditionally prefixing closing >
characters with a whitespace in type names.
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 problem[^1]:
'>'
The first step has a surprisingly obvious solution: Generic type parameters can be referenced via the $T<n>
macros. Wrapping a macro inside quotation marks won't inhibit macro expansion, and "$T2"
evaluates to a character string holding the literal name of the second type parameter. This is supported across all debuggers (WinDbg/CDB/VS).
Attempting to implement step two is when debuggers start showing divergent behavior: In lieu of a strrchr
intrinsic (to find the last occurrence of a character) we have to determine the length of the string instead and subsequently reference the character at index len - 1
. The strlen
intrinsic is available on all debuggers and strlen("$T2")
faithfully returns the length of the literal type name.
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., &"$T2"[0]
. The only alternative I could think up is to implement an intrinsic that takes a char const*
parameter and rely on C-style implicit array-to-pointer decay to arrive at a pointer. The result follows the persistent theme: It works in VS but not the other debuggers.
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)?
[^1]: The idea here is to use this predicate in an <Exec>
's Condition
attribute to delegate to one of two discrete intrinsics (e.g., cast_to_internal_generic()
and cast_to_internal_nongeneric()
).
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:![screenshot](https://user-images.githubusercontent.com/119948/140010898-b22f52fd-13c1-4231-b19f-453c930d9b97.jpeg)
originally reported here https://internals.rust-lang.org/t/feature-request-debug-visualizer-for-btreemap-set/15543