Infinite loop in TabBar resizing

hanatos commented 2 years ago

Version/Branch of Dear ImGui:

Version: "1.89 WIP" e13913ed Branch: master

Back-end/Renderer/Compiler/OS

Back-ends: imgui_impl_vulkan.cpp + imgui_impl_glfw.cpp Compiler: clang Operating System: linux/debian sid

My Issue/Question:

since i updated to a new version of imgui, i'm experiencing random hangs at times. i think i tracked the issue down to commit c4b91017, in particular the excess width handling in the TabBar. what seems to happen when i step through the code in gdb is that

https://github.com/ocornut/imgui/blob/master/imgui_widgets.cpp#L1578 <= this becomes an infinite while loop (in current master same code)

because in the following the line if (items[n].Width + 1.0f <= items[n].InitialWidth) is always unfortunate enough to only contain fractional bits, so the +1.0f case never triggers:

Thread 1 "vkdt" received signal SIGINT, Interrupt.
0x00005555555f527e in ImGui::ShrinkWidths (items=0x55555a389dd0, count=4, width_excess=0.760025024) at ../ext/imgui/imgui_widgets.cpp:1581
1581                if (items[n].Width + 1.0f <= items[n].InitialWidth)
(gdb) p items[n]
$1 = {Index = 3, Width = 100, InitialWidth = 100.479996}
(gdb)

today i can always reproduce it with my settings and screen resolution using https://github.com/hanatos/vkdt/commits/master but i'm hoping it would be possible to fix this conceptually so i don't have to prepare a minimal example. for context, i have four tabs that almost fill the width of the containing window. they all run into this rounding issue:

(gdb) p items[0]
$2 = {Index = 2, Width = 163, InitialWidth = 163.480011}
(gdb) p items[1]
$3 = {Index = 0, Width = 119, InitialWidth = 119.479996}
(gdb) p items[2]
$4 = {Index = 1, Width = 107, InitialWidth = 107.479996}
(gdb) p items[3]
$5 = {Index = 3, Width = 100, InitialWidth = 100.479996}

for now i have commented out the while(width_excess > 0.0f) loop to get back a working version.

ocornut commented 2 years ago

Interesting. Should be easy to repro/fix but I’ll only be able to do it tomorrow.

Could you also confirm the g.FontSize value? I know we have a whole range of subtle bugs with unrounded font sizes, I wonder if that’s one of them.

ocornut commented 2 years ago

Thanks for the careful and quality bug report :)

Pushed what I think should be a fix: b137f31 Amending c4b91017. There were 2 bugs.

Bug 1 was we erroneously over-distributed remainder. At minima, this:

    while (width_excess > 0.0f)
        for (int n = 0; n < count; n++)

Should have been

    while (width_excess > 0.0f)
        for (int n = 0; n < count && width_excess > 0.0f; n++)

Without it right-most tab often ended up slightly outside the tab-bar right-most edge.

Bug 2 is that issue you mentioned. I believe I fixed it by changing 3 thresholds.

Still interested in the answer to this:

Could you also confirm the g.FontSize value? I know we have a whole range of subtle bugs with unrounded font sizes, I wonder if that’s one of them.

Repro

ImGui::SetNextWindowSize(ImVec2(518.0f, 500.0f));
ImGui::Begin("Bug #5652");
if (ImGui::BeginTabBar("blah", ImGuiTabBarFlags_Reorderable))
{
    ImGui::SetNextItemWidth(163.480011f);
    if (ImGui::BeginTabItem("1"))
        ImGui::EndTabItem();

    ImGui::SetNextItemWidth(119.479996f);
    if (ImGui::BeginTabItem("2"))
        ImGui::EndTabItem();

    ImGui::SetNextItemWidth(107.479996f);
    if (ImGui::BeginTabItem("3"))
        ImGui::EndTabItem();

    ImGui::SetNextItemWidth(100.479996f);
    if (ImGui::BeginTabItem("4"))
        ImGui::EndTabItem();
    ImGui::EndTabBar();
}
ImGui::End();

hanatos commented 2 years ago

thanks for the fast reply and the fast fix! i can confirm that using the latest imgui master works as expected now on my side.

indeed my font sizes are chosen rather carelessly when it comes to rounding. in particular in that part of the code, g.FontSize = 26.181818 and in general i am working with font sizes 26.1818 39.2727 52.3636. i have no problem rounding these, i wasn't aware that there may be subtle issues (for high-dpi screens i am scaling these with respect to window height instead of an absolute number of pixels).

On Wed, Sep 7, 2022 at 12:24 PM omar @.***> wrote:

Thanks for the careful and quality bug report :)

Pushed what I think should be a fix: b137f31 https://github.com/ocornut/imgui/commit/b137f31b8c939eb35dc01e77322e48245318c393 Amending c4b9101 https://github.com/ocornut/imgui/commit/c4b91017599e222d538c917930d70f7fe0a04de1. There were 2 bugs.

Bug 1 was we erroneously over-distributed remainder. At minima, this:
while (width_excess > 0.0f)

    for (int n = 0; n < count; n++)
Should have been
while (width_excess > 0.0f)

    for (int n = 0; n < count && width_excess > 0.0f; n++)
Without it right-most tab often ended up slightly outside the tab-bar right-most edge.

Bug 2 is that issue you mentioned. I believe I fixed it by changing 3 thresholds.

Still interested in the answer to this:

Could you also confirm the g.FontSize value? I know we have a whole range of subtle bugs with unrounded font sizes, I wonder if that’s one of them.

Repro

ImGui::SetNextWindowSize(ImVec2(518.0f, 500.0f)); ImGui::Begin("Bug #5652"); if (ImGui::BeginTabBar("blah", ImGuiTabBarFlags_Reorderable))

{
ImGui::SetNextItemWidth(163.480011f);

if (ImGui::BeginTabItem("1"))

    ImGui::EndTabItem();

ImGui::SetNextItemWidth(119.479996f);

if (ImGui::BeginTabItem("2"))

    ImGui::EndTabItem();

ImGui::SetNextItemWidth(107.479996f);

if (ImGui::BeginTabItem("3"))

    ImGui::EndTabItem();

ImGui::SetNextItemWidth(100.479996f);

if (ImGui::BeginTabItem("4"))

    ImGui::EndTabItem();

ImGui::EndTabBar();
} ImGui::End();

— Reply to this email directly, view it on GitHub https://github.com/ocornut/imgui/issues/5652#issuecomment-1239201457, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMAKKPHPPDS3ATB7FWM6BLV5BUN7ANCNFSM6AAAAAAQGDSQGI . You are receiving this because you authored the thread.Message ID: @.***>

ocornut commented 2 years ago

We have variety of known and unknown bugs (just the other days I noticed clipper has issues with non-integer line size) so I would suggest rounding the size. Otherwise be my guest and run with it and happy to hear bugs reported :)

samyuu commented 2 years ago

I appologize for the very lackluster report in comparison as I have neither a minimal example to show nor a proposal for a fix. I would however like to mention that from my testing this issue still happens (though possible less often) with both b137f31b8c939eb35dc01e77322e48245318c393 and c4b91017599e222d538c917930d70f7fe0a04de1 in place (manually merged by me into the latest docking branch 18814 with all master branch changes up to 18817).

I find myself in the admititly niche situtation of having implemented a dynamic animated UI scaling system which works by rebuilding fonts at a larger (rounded) size and then inversely scaling IO.FontGlobalScale afterwards to smoothly transition to a new screen size. For my own purposes as I'm only animating temporarily, adding a max loop safety counter is enough to fix the freezing and therefore avoid the problem. https://user-images.githubusercontent.com/25674161/189280636-b6c5accc-6691-4305-b074-f2a5e3d9af5f.mp4

Perhaps it would be a good idea to add a max loop counter into the main branches too, at least with an IM_ASSERT to automatically detect this in the future and make absolutely sure that an infinite loop can never happen again (?)

ocornut commented 2 years ago

On one of those hangs, please provide the values you did provide (items array) + width_excess value at the time of calling the function (from caller function) + GImGui->CurrentWindow->Size.x for good measure. Thanks!

hanatos commented 2 years ago

so probably what happens is that there is more than one pixel width_excess but all the individual tabs still only receive less than one pixel offset? how about a single-pass floyd-steinberg diffusion instead?

    // Round width and redistribute remainder
    // floyd steinberg diffusion:
    width_excess = 0.0f;
    for(int n = 0; n < count; n++)
    {
        items[n].Width += width_excess;
        float width_rounded = ImFloor(items[n].Width);
        width_excess += items[n].Width - width_rounded;
        items[n].Width = width_rounded;
    }

(patch attached, had to gzip it so github would accept it) 0001-tabbar-propose-to-distribute-widths-via-floyd-steinb.patch.gz

samyuu commented 2 years ago

These are two example inputs that lead to inifinite loops for me with the code in its current state:

// GImGui->CurrentWindow->Size = { 1269, 956 }
ImGuiShrinkWidthItem testItemsA[] =
{
    { 0, 99.0000000f, 99.0000000f },
    { 1, 110.952225f, 110.952225f },
    { 2, 84.9522247f, 84.9522247f },
    { 3, 144.952225f, 144.952225f },
};
ImGui::ShrinkWidths(testItemsA, 4, 1.80895996f);

// GImGui->CurrentWindow->Size = { 1269, 956 }
ImGuiShrinkWidthItem testItemsB[] =
{
    { 0, 99.0000000f, 99.0000000f },
    { 1, 110.953949f, 110.953949f },
    { 2, 84.9539490f, 84.9539490f },
    { 3, 144.953949f, 144.953949f },
};
ImGui::ShrinkWidths(testItemsB, 4, 1.81582642f);

From my limited testing the single pass floyd steinberg diffusion approach appears to be working quite well here without any obvious issues 👍🏿

ocornut commented 2 years ago

These are two example inputs that lead to inifinite loops for me with the code in its current state:

Thanks. I can repro with the low-level examples calling ShrinkWidths(). but not with a window (unsure how 1269 width would lead to a reduction here?). I'd need to see a tab-bar to validate a code change. Trying to set up a repro...

ocornut commented 2 years ago

so probably what happens is that there is more than one pixel width_excess but all the individual tabs still only receive less than one pixel offset? how about a single-pass floyd-steinberg diffusion instead?

That suggestion change makes unrelated tabs subtly move/wobble around while crossing the resize point so it isn't correct.

ocornut commented 2 years ago

There are two issues actually.

1) ~~@hanatos and @samyuu would you mind trying with this version of the function?~~ (see next post)

// Shrink excess width from a set of item, by removing width from the larger items first.
// Set items Width to -1.0f to disable shrinking this item.
void ImGui::ShrinkWidths(ImGuiShrinkWidthItem* items, int count, float width_excess)
{
    if (count == 1)
    {
        if (items[0].Width >= 0.0f)
            items[0].Width = ImMax(items[0].Width - width_excess, 1.0f);
        return;
    }
    ImQsort(items, (size_t)count, sizeof(ImGuiShrinkWidthItem), ShrinkWidthItemComparer);
    int count_same_width = 1;
    float width_excess_remainder = 0.0f;
    while (width_excess > 0.0f && count_same_width < count)
    {
        while (count_same_width < count && items[0].Width <= items[count_same_width].Width)
            count_same_width++;
        float max_width_to_remove_per_item = (count_same_width < count && items[count_same_width].Width >= 0.0f) ? (items[0].Width - items[count_same_width].Width) : (items[0].Width - 1.0f);
        if (max_width_to_remove_per_item <= 0.0f)
            break;
        float width_to_remove_per_item = ImMin(width_excess / count_same_width, max_width_to_remove_per_item);
        for (int item_n = 0; item_n < count_same_width; item_n++)
        {
            items[item_n].Width -= width_to_remove_per_item;
            width_excess -= width_to_remove_per_item;
            width_excess_remainder += items[item_n].Width - ImFloor(items[item_n].Width);
        }
    }

    // Round width and redistribute remainder
    // Ensure that e.g. the right-most tab of a shrunk tab-bar always reaches exactly at the same distance from the right-most edge of the tab bar separator.
    for (int n = 0; n < count; n++)
        items[n].Width = ImFloor(items[n].Width);
    while (width_excess_remainder >= 1.0f)
        for (int n = 0; n < count && width_excess_remainder >= 1.0f; n++)
            if (items[n].Width + 1.0f <= items[n].InitialWidth)
            {
                items[n].Width += 1.0f;
                width_excess_remainder -= 1.0f;
            }
}

2) We'll need to round before shrinking anyway, otherwise there's a subtle change of table size when resizing.

ocornut commented 2 years ago

Disregard my function (1) for now I found another issue in some cases it pushes back right too much.

ocornut commented 2 years ago

Can you try this version.? Only replacing the final loop from the current commit:

    while (width_excess > 0.0f)
        for (int n = 0; n < count && width_excess > 0.0f; n++)
        {
            float width_to_add = ImMin(items[n].InitialWidth - items[n].Width, 1.0f);
            items[n].Width += width_to_add;
            width_excess -= width_to_add;
        }

The thing I checked are:

Using rounded widths, the right most tabs is always at the same pixel distance to the right of the tab bar.
Using rounded widths, the relative spacing between each tabs never changes.
Can't get it to infinite loop with non-rounded widths.

Issues (that are not new)

Using non-rounded widths result in subtle offset when starting to resize, because we round output at this point (not new), technically easier to fix, could do.
Using non-rounded widths still result in subtle wobbling but that's due to layout system (not new)

It's not perfect for non-rounded width but nothing in Dear ImGui currently is (*)

* Amusingly, at the time I am typing this into Firefox, the textbox height keeps resizing back-and-worth between +0 and +1 pixels whenever I type.. Guess some other code has tricky rounding issue...

ocornut commented 2 years ago

I pushed my second fix attempt 52d9ee0d curious to see if confirmed.

samyuu commented 2 years ago

Testing with the latest changes as per 52d9ee0dc2c5db5b08098fc2f219e9870ef8e3a3, under my setup everything appears to be working correctly now and I wasn't able to trigger any infinite loops either. For my own peace of mind I'm still rolling with an extra safety check + an assert but I believe this issue is fully resolved now.

Thank you for the quick fix and this amazing library!

hanatos commented 2 years ago

can't reproduce any more now.. i'm always slightly worried about while(something) loops but this seems to work, thanks again.

ocornut / imgui

Infinite loop in TabBar resizing #5652