TreeNode: IM_ASSERT(data->ID == window->IDStack.back()) in TreePop() fires on trees deeper than 32 levels when hierarchy lines are enabled

[lasrod]

Version/Branch of Dear ImGui:

Version 1.93.0 WIP (19294), Branch: master @ 46d39d5. Unmodified. Also reproduced on 1.92.7 (docking).

Back-ends:

n/a — reproduced with no backend (CreateContext() + NewFrame() only). Originally hit in an app using imgui_impl_glfw.cpp + imgui_impl_opengl3.cpp.

Compiler, OS:

Windows 11 + Clang 22.1.4, and Ubuntu 24.04 + GCC 14.

Details:

My Issue/Question:

With style.TreeLinesFlags = ImGuiTreeNodeFlags_DrawLinesFull (or DrawLinesToNodes) and a tree nested more than 32 levels deep in a window too short to show all of it, TreePop() asserts:

Assertion failed: data->ID == window->IDStack.back(), imgui_widgets.cpp, line 7293

In a build with asserts disabled there is no assert, but TreePop() pops the wrong ImGuiTreeNodeStackData for the remaining levels: hierarchy lines are drawn from the wrong parent, and g.TreeNodeStack is left with 5–8 stale entries at the end of the frame (cleared in NewFrame(), so it does not accumulate).

Cause

TreeNodeBehavior() and TreePop() index a depth bitmask with 1 << window->DC.TreeDepth on a signed int. The comment above TreeNodeStoreStackData() says:

// Currently only supports 32 level deep and we are fine with (1 << Depth) overflowing into a zero, easy to increase.

That assumption does not hold on x86-64 or AArch64, where the shift count is masked to 5 bits. 1 << 32 evaluates to 1, not 0 (verified with a runtime, non-constant-folded shift):

1 << 31 = 0x80000000
1 << 32 = 0x00000001     <- aliases onto depth 0, does not vanish
1 << 33 = 0x00000002

So depth 32 aliases onto depth 0. Two things follow:

1. A node at depth 32 sets bit 0 in TreeHasStackDataDepthMask, and its TreePop() then clears bit 0 — which belongs to depth 0. Depth 0's own TreePop() therefore skips the whole if (window->DC.TreeHasStackDataDepthMask & tree_depth_mask) block: g.TreeNodeStack.pop_back() never runs, and neither does TreeNodeDrawLineToTreePop(), so the root's vertical line is not drawn. Measured after all TreePop()s in one frame:

   32 levels: after push Size=32 mask=0xFFFFFFFF | after pop Size=0 mask=0x00000000   correct
   33 levels: after push Size=33 mask=0xFFFFFFFF | after pop Size=1 mask=0x00000000   entry never popped
   

2. The assert above is the same aliasing in the other direction. A node at depth >= 32 that is clipped stores no stack data, but its TreePop() still computes bit 0, sees depth 0's bit set, and pops an entry belonging to a different node — so data->ID no longer matches IDStack.back(). This is why the window has to be too short to show the whole tree: it is what makes the deep nodes clipped while the shallow ones are not. In the repro below (500x650 window, ~19px rows) it starts at 38 levels; deeper trees or shorter windows trigger it sooner.

Separately, imgui_widgets.cpp:7002 evaluates (1 << (window->DC.TreeDepth - 1)) inside the if (!is_visible) branch before anything checks TreeDepth > 0, so a clipped root-level node with DrawLinesToNodes shifts by -1. That one needs no deep nesting at all — just a scrolled list of root-level TreeNodes.

What is not affected

At the default style.TreeLinesFlags = ImGuiTreeNodeFlags_DrawLinesNone, TreeNodeStoreStackData() is never called, TreeHasStackDataDepthMask stays 0, and the aliased bit is never consulted. I ran the same repro at the default style up to 40 levels: no assert, g.TreeNodeStack balances, nothing observably wrong. The undefined shift still executes (which is how we found this — a UBSan job on a deep tree), but at the default style that is all it does. Presumably that is why this has gone unnoticed since tree lines landed.

Minimal, Complete and Verifiable Example code:

(1) The assert. Paste into any example app's frame:

ImGui::GetStyle().TreeLinesFlags = ImGuiTreeNodeFlags_DrawLinesFull;

ImGui::SetNextWindowSize(ImVec2(500, 650));       // deliberately too short for 40 rows
ImGui::Begin("Deep");
int opened = 0;
for (int i = 0; i < 40; i++) {
    ImGui::SetNextItemOpen(true, ImGuiCond_Always);
    if (!ImGui::TreeNode((void*)(intptr_t)i, "L%d", i)) break;
    opened++;
}
for (int i = 0; i < opened; i++)
    ImGui::TreePop();                             // asserts at imgui_widgets.cpp:7293
ImGui::End();

With 40 changed to 32 it is clean, so the threshold is the mask width rather than anything about the loop.

(2) The leaked TreeNodeStack entry, without clipping — same as above but in a window tall enough to show all 33 rows (I used DisplaySize 1200x4000 and an 800x3900 window). g.TreeNodeStack.Size is 1 after the pops instead of 0; at 32 levels it is 0.

(3) The negative shift, at depth 0:

ImGui::GetStyle().TreeLinesFlags = ImGuiTreeNodeFlags_DrawLinesToNodes;

ImGui::SetNextWindowSize(ImVec2(300, 120));       // small, so most roots are clipped
ImGui::Begin("Clipped roots");
for (int i = 0; i < 60; i++) {
    ImGui::SetNextItemOpen(true, ImGuiCond_Always);
    if (ImGui::TreeNode((void*)(intptr_t)i, "root %d", i)) {
        ImGui::TextUnformatted("child");
        ImGui::TreePop();                         // imgui_widgets.cpp:7002 -> shift exponent -1
    }
}
ImGui::End();

(4) The undefined shift on its own, no widgets or style needed — 33 levels is the threshold, 32 is clean:

ImGui::Begin("Deep");
for (int i = 0; i < 33; i++) ImGui::TreePush("x");
for (int i = 0; i < 33; i++) ImGui::TreePop();    // imgui_widgets.cpp:7288 -> shift exponent 32
ImGui::End();

Suggested fix

Your call entirely, but the smallest change that makes the existing comment's intent actually true is a helper returning 0 out of range, plus not storing stack data that can never be popped:

+// Depth bitmask for TreeHasStackDataDepthMask / TreeRecordsClippedNodesY2Mask.
+// Only 32 levels are trackable: out-of-range depths (>= 32, or -1 for a depth-0 node's parent)
+// yield 0, which is the "overflowing into a zero" behaviour the code below already assumes.
+static inline ImU32 TreeNodeGetDepthMask(int depth)
+{
+    return ((unsigned int)depth < 32u) ? (1u << depth) : 0u;
+}
+
 // Store ImGuiTreeNodeStackData for just submitted node.
 // Currently only supports 32 level deep and we are fine with (1 << Depth) overflowing into a zero, easy to increase.
 static void TreeNodeStoreStackData(ImGuiTreeNodeFlags flags, float x1)
@@
-    window->DC.TreeHasStackDataDepthMask |= (1 << window->DC.TreeDepth);
+    window->DC.TreeHasStackDataDepthMask |= TreeNodeGetDepthMask(window->DC.TreeDepth);
     if (flags & ImGuiTreeNodeFlags_DrawLinesToNodes)
-        window->DC.TreeRecordsClippedNodesY2Mask |= (1 << window->DC.TreeDepth);
+        window->DC.TreeRecordsClippedNodesY2Mask |= TreeNodeGetDepthMask(window->DC.TreeDepth);
@@ bool ImGui::TreeNodeBehavior(...)
         if ((flags & ImGuiTreeNodeFlags_NavLeftJumpsToParent) && !g.NavIdIsAlive)
             if (g.NavMoveDir == ImGuiDir_Left && g.NavWindow == window && NavMoveRequestButNoResultYet())
                 store_tree_node_stack_data = true;
+        if (window->DC.TreeDepth >= 32) // Mask only tracks 32 levels: past that, degrade instead of aliasing.
+            store_tree_node_stack_data = false;
     }
@@
-        if ((flags & ImGuiTreeNodeFlags_DrawLinesToNodes) && (window->DC.TreeRecordsClippedNodesY2Mask & (1 << (window->DC.TreeDepth - 1))))
+        if ((flags & ImGuiTreeNodeFlags_DrawLinesToNodes) && (window->DC.TreeRecordsClippedNodesY2Mask & TreeNodeGetDepthMask(window->DC.TreeDepth - 1)))
@@
-                window->DC.TreeRecordsClippedNodesY2Mask &= ~(1 << (window->DC.TreeDepth - 1)); // Done
+                window->DC.TreeRecordsClippedNodesY2Mask &= ~TreeNodeGetDepthMask(window->DC.TreeDepth - 1); // Done
@@ void ImGui::TreeNodeDrawLineToChildNode(...)
-    if (window->DC.TreeDepth == 0 || (window->DC.TreeHasStackDataDepthMask & (1 << (window->DC.TreeDepth - 1))) == 0)
+    if (window->DC.TreeDepth == 0 || (window->DC.TreeHasStackDataDepthMask & TreeNodeGetDepthMask(window->DC.TreeDepth - 1)) == 0)
@@ void ImGui::TreePop()
-    ImU32 tree_depth_mask = (1 << window->DC.TreeDepth);
+    ImU32 tree_depth_mask = TreeNodeGetDepthMask(window->DC.TreeDepth);

With this applied, repros (1)–(4) are all clean, g.TreeNodeStack balances at every depth I tried (up to 200), and depths 0–31 are unchanged. The behavioural cost is that hierarchy lines stop below depth 32 instead of aliasing, which is what "only supports 32 level deep" already promises. Widening both masks to ImU64 (as imgui_internal.h already notes: "Could be turned into a ImU64 if necessary") is orthogonal and would move the wall to 64 with the same guard still needed.

Happy to open a PR if you'd prefer.

[ocornut]

Hello,

Did you actually naturally hit the issue in your app, or is that the result of a preemptive search for issues? If the earlier, can you provide more details about your context?

Did you use an LLM to write the message above?

Cheers.

[lasrod]

Hello @ocornut,

The undefined behaviour hit for real, in our CI. The first run of a new ASan + UBSan job flagged one thing across 1,232 tests, inside our own tree panel.

The assert did not. I built that reproduction afterwards, to test whether the shift really mattered. It has never happened in production for us. But it is not an unlikely scenario for the application we are building, so for that reason I thought it was worth filing here.

Our software that we develop builds a tree of argument nodes, and the tree view mirrors that structure one to one in the tree view. Reaching depth 32 is realistic for us, and the shift breaks at 33, which is why we test for it.

Yes, an LLM was used for the message above. But I did not just post what it first proposed. I challenged it to prove the issue was real before I filed anything. The assert, the depth sweep and the patch verification are what came out of that.

[ocornut]

Thanks for the clarification!

I’m thinking the reasonable pragmatic answer may be make necessary tweaks to avoid reported UB., and then perhaps up this to 64-bits. I tend wary even inline helpers in hot paths like TreeNodeBehavior() but it’s solvable.

Unfortunately my holidays started today so it may need to wait a few weeks.

[lasrod]

@ocornut Thank you for the reply!

Holidays are important. No rush, enjoy vacation!

I am happy to help to resolve this issue in the best way possible. I am also on vacation now so will likely not spend much time on this in the next week or two but could for sure dive into this in more depth later with a better proposal than what has been given now.