Fix transient_for endless loop

Other approaches would be:
- Slow/fast pointer technique.
- Using a set/associative map to save 'seen' nodes. i3 does not have
  such data structure.

Counting the total amount of windows is the simpler to implement.

I've also extracted the logic in a function and re-used it in render.c.

Fixes #4404

6 files changed, 92 insertions, 45 deletions

diff --git a/include/con.h b/include/con.h
index d8330098..3cea6780 100644
--- a/include/con.h
+++ b/include/con.h
@@ -209,6 +209,14 @@ Con *con_by_frame_id(xcb_window_t frame);
 Con *con_by_mark(const char *mark);
 
 /**
+ * Start from a container and traverse the transient_for linked list. Returns
+ * true if target window is found in the list. Protects againsts potential
+ * cycles.
+ *
+ */
+bool con_find_transient_for_window(Con *start, xcb_window_t target);
+
+/**
  * Returns true if and only if the given containers holds the mark.
  *
  */
diff --git a/release-notes/bugfixes/3-transient_for b/release-notes/bugfixes/3-transient_for
new file mode 100644
index 00000000..c652874f
--- /dev/null
+++ b/release-notes/bugfixes/3-transient_for
@@ -0,0 +1 @@
+Fix endless loop with transient_for windows
diff --git a/src/con.c b/src/con.c
index 18338235..d8964471 100644
--- a/src/con.c
+++ b/src/con.c
@@ -731,6 +731,41 @@ Con *con_by_mark(const char *mark) {
 }
 
 /*
+ * Start from a container and traverse the transient_for linked list. Returns
+ * true if target window is found in the list. Protects againsts potential
+ * cycles.
+ *
+ */
+bool con_find_transient_for_window(Con *start, xcb_window_t target) {
+    Con *transient_con = start;
+    int count = con_num_windows(croot);
+    while (transient_con != NULL &&
+           transient_con->window != NULL &&
+           transient_con->window->transient_for != XCB_NONE) {
+        DLOG("transient_con = 0x%08x, transient_con->window->transient_for = 0x%08x, target = 0x%08x\n",
+             transient_con->window->id, transient_con->window->transient_for, target);
+        if (transient_con->window->transient_for == target) {
+            return true;
+        }
+        Con *next_transient = con_by_window_id(transient_con->window->transient_for);
+        if (next_transient == NULL) {
+            break;
+        }
+        /* Some clients (e.g. x11-ssh-askpass) actually set WM_TRANSIENT_FOR to
+         * their own window id, so break instead of looping endlessly. */
+        if (transient_con == next_transient) {
+            break;
+        }
+        transient_con = next_transient;
+
+        if (count-- <= 0) { /* Avoid cycles, see #4404 */
+            break;
+        }
+    }
+    return false;
+}
+
+/*
  * Returns true if and only if the given containers holds the mark.
  *
  */
diff --git a/src/manage.c b/src/manage.c
index ee046f0f..5f9aeb53 100644
--- a/src/manage.c
+++ b/src/manage.c
@@ -485,34 +485,17 @@ void manage_window(xcb_window_t window, xcb_get_window_attributes_cookie_t cooki
         (cwindow->leader != XCB_NONE &&
          cwindow->leader != cwindow->id &&
          con_by_window_id(cwindow->leader) != NULL)) {
-        LOG("This window is transient for another window, setting floating\n");
+        DLOG("This window is transient for another window, setting floating\n");
         want_floating = true;
 
         if (config.popup_during_fullscreen == PDF_LEAVE_FULLSCREEN &&
             fs != NULL) {
-            LOG("There is a fullscreen window, leaving fullscreen mode\n");
+            DLOG("There is a fullscreen window, leaving fullscreen mode\n");
             con_toggle_fullscreen(fs, CF_OUTPUT);
         } else if (config.popup_during_fullscreen == PDF_SMART &&
                    fs != NULL &&
                    fs->window != NULL) {
-            i3Window *transient_win = cwindow;
-            while (transient_win != NULL &&
-                   transient_win->transient_for != XCB_NONE) {
-                if (transient_win->transient_for == fs->window->id) {
-                    LOG("This floating window belongs to the fullscreen window (popup_during_fullscreen == smart)\n");
-                    set_focus = true;
-                    break;
-                }
-                Con *next_transient = con_by_window_id(transient_win->transient_for);
-                if (next_transient == NULL)
-                    break;
-                /* Some clients (e.g. x11-ssh-askpass) actually set
-                 * WM_TRANSIENT_FOR to their own window id, so break instead of
-                 * looping endlessly. */
-                if (transient_win == next_transient->window)
-                    break;
-                transient_win = next_transient->window;
-            }
+            set_focus = con_find_transient_for_window(nc, fs->window->id);
         }
     }
 
diff --git a/src/render.c b/src/render.c
index cf4fd45f..cc1c01f8 100644
--- a/src/render.c
+++ b/src/render.c
@@ -226,34 +226,12 @@ static void render_root(Con *con, Con *fullscreen) {
                 }
 
                 Con *floating_child = con_descend_focused(child);
-                Con *transient_con = floating_child;
-                bool is_transient_for = false;
-                while (transient_con != NULL &&
-                       transient_con->window != NULL &&
-                       transient_con->window->transient_for != XCB_NONE) {
-                    DLOG("transient_con = 0x%08x, transient_con->window->transient_for = 0x%08x, fullscreen_id = 0x%08x\n",
-                         transient_con->window->id, transient_con->window->transient_for, fullscreen->window->id);
-                    if (transient_con->window->transient_for == fullscreen->window->id) {
-                        is_transient_for = true;
-                        break;
-                    }
-                    Con *next_transient = con_by_window_id(transient_con->window->transient_for);
-                    if (next_transient == NULL)
-                        break;
-                    /* Some clients (e.g. x11-ssh-askpass) actually set
-                     * WM_TRANSIENT_FOR to their own window id, so break instead of
-                     * looping endlessly. */
-                    if (transient_con == next_transient)
-                        break;
-                    transient_con = next_transient;
-                }
-
-                if (!is_transient_for)
-                    continue;
-                else {
+                if (con_find_transient_for_window(floating_child, fullscreen->window->id)) {
                     DLOG("Rendering floating child even though in fullscreen mode: "
                          "floating->transient_for (0x%08x) --> fullscreen->id (0x%08x)\n",
                          floating_child->window->transient_for, fullscreen->window->id);
+                } else {
+                    continue;
                 }
             }
             DLOG("floating child at (%d,%d) with %d x %d\n",
diff --git a/testcases/t/316-transient-for-loop.t b/testcases/t/316-transient-for-loop.t
new file mode 100644
index 00000000..336a8d8d
--- /dev/null
+++ b/testcases/t/316-transient-for-loop.t
@@ -0,0 +1,42 @@
+#!perl
+# vim:ts=4:sw=4:expandtab
+#
+# Please read the following documents before working on tests:
+# • https://build.i3wm.org/docs/testsuite.html
+#   (or docs/testsuite)
+#
+# • https://build.i3wm.org/docs/lib-i3test.html
+#   (alternatively: perldoc ./testcases/lib/i3test.pm)
+#
+# • https://build.i3wm.org/docs/ipc.html
+#   (or docs/ipc)
+#
+# • http://onyxneon.com/books/modern_perl/modern_perl_a4.pdf
+#   (unless you are already familiar with Perl)
+#
+# Test that i3 does not get stuck in an endless loop between two windows that
+# set transient_for for each other.
+# Ticket: #4404
+# Bug still in: 4.20-69-g43e805a00
+#
+use i3test i3_config => <<EOT;
+# i3 config file (v4)
+font -misc-fixed-medium-r-normal--13-120-75-75-C-70-iso10646-1
+
+popup_during_fullscreen smart;
+EOT
+
+my $fs = open_window;
+cmd 'fullscreen enable';
+
+my $w1 = open_window({ dont_map => 1 });
+my $w2 = open_window({ dont_map => 1 });
+
+$w1->transient_for($w2);
+$w2->transient_for($w1);
+$w1->map;
+$w2->map;
+
+does_i3_live;
+
+done_testing;