[vlc-devel] [PATCH] qt: playlist: fix stack overflow

[Hugo Beauzée-Luyssen]

On Tue, Nov 7, 2017, at 09:53 AM, Romain Vimont wrote:
> The playlist tree may be arbitrary deep, so traversing it recursively
> may lead to stack overflow.
> 
> Traverse it iteratively instead.
> 
> Fixes #18376
> ---
>  .../gui/qt/components/playlist/playlist_model.cpp  | 30
>  +++++++++++++++-------
>  1 file changed, 21 insertions(+), 9 deletions(-)
> 
> diff --git a/modules/gui/qt/components/playlist/playlist_model.cpp
> b/modules/gui/qt/components/playlist/playlist_model.cpp
> index 2b6d0e1ccc..99e4c8f942 100644
> --- a/modules/gui/qt/components/playlist/playlist_model.cpp
> +++ b/modules/gui/qt/components/playlist/playlist_model.cpp
> @@ -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;
>  }
> -- 
> 2.11.0
> 
> _______________________________________________
> vlc-devel mailing list
> To unsubscribe or modify your subscription options:
> https://mailman.videolan.org/listinfo/vlc-devel

LGTM

-- 
  Hugo Beauzée-Luyssen
  hugo at beauzee.fr