qt: playlist: fix stack overflow
authorRomain Vimont <rom@rom1v.com>
Tue, 7 Nov 2017 08:53:46 +0000 (09:53 +0100)
committerHugo Beauzée-Luyssen <hugo@beauzee.fr>
Tue, 7 Nov 2017 13:01:37 +0000 (14:01 +0100)
The playlist tree may be arbitrary deep, so traversing it recursively
may lead to stack overflow.

Traverse it iteratively instead.

Fixes #18376

Signed-off-by: Hugo Beauzée-Luyssen <hugo@beauzee.fr>
modules/gui/qt/components/playlist/playlist_model.cpp

index 2b6d0e1..99e4c8f 100644 (file)
@@ -41,6 +41,7 @@
 #include <assert.h>
 #include <QFont>
 #include <QAction>
+#include <QStack>
 
 /*************************************************************************
  * Playlist model implementation
@@ -518,20 +519,31 @@ PLItem *PLModel::findByPLId( PLItem *root, int i_id ) const
     if( root->id() == i_id )
         return root;
 
-    QList<AbstractPLItem *>::iterator it = root->children.begin();
-    while ( it != root->children.end() )
+    /* traverse the tree (in depth first) iteratively to avoid stack overflow */
+
+    struct RemainingChildren {
+        QList<AbstractPLItem *>::const_iterator next;
+        QList<AbstractPLItem *>::const_iterator end;
+    };
+
+    QStack<RemainingChildren> stack;
+    if( root->childCount() )
+        stack.push( {root->children.cbegin(), root->children.cend()} );
+
+    while ( !stack.isEmpty() )
     {
-        PLItem *item = static_cast<PLItem *>(*it);
+        RemainingChildren &remainingChildren = stack.top();
+
+        PLItem *item = static_cast<PLItem *>( *remainingChildren.next );
         if( item->id() == i_id )
             return item;
 
+        if( ++remainingChildren.next == remainingChildren.end )
+            /* there are no more children at this depth level */
+            stack.pop();
+
         if( item->childCount() )
-        {
-            PLItem *childFound = findByPLId( item, i_id );
-            if( childFound )
-                return childFound;
-        }
-        ++it;
+            stack.push( {item->children.cbegin(), item->children.cend()} );
     }
     return NULL;
 }