Bug#802648: [Aptitude-devel] Bug#802648: aptitude: definite loop when searching "youk" in "youtube-dl" package info page

[Manuel A. Fernandez Montecelo]

Control: tags -1 + pending

2016-06-12 13:25 Manuel A. Fernandez Montecelo:

I've been investigating this again and I believe that it's actually a
problem with the cwidget library, that has happened since forever.

This happens also for example with devscripts and rhythmbox-plugins,
which have a long description which makes the main/first subtree (the
one with the package name, the second subtree is "Depends") to also
"fill" my terminal (expand more than a screenful vertically), like
youtube-dl.  It doesn't happen with libwiretap5 even if the description
is quite long, for example.

I think that it has to do with how the cwidget implementation moves the
view to jump to where the term being searched appears, and that gets
confused when the contents are off the screen or something similar.  The
backtrace points to line 854 in ./src/cwidget/widgets/tree.cc with the
line:

while(curr!=start && !matches(*curr))

and with aptitude's menu_tree.cc, line 82.


Searching for "yo" in "youtube-dl" screen doesn't produce the desired
effect (I presume), of searching e.g. inside the Description field.

When the screen starts at line "zero" [1], with incsearch enabled, "y"
jumps to the line below [2], after "yo" jumps to the last line (below
[3]), after "you" the same (and at this point it didn't hang yet, one
can delete with backspace etc).  With "youk" enters the infinite loop.

If one presses "yok", or "youk", it also triggers the
infinite loop.

It will need quite some debugging, and probably a new cwidget release to
get this fixed.


Marking as pending.  I append here the commit message:



Avoid endless loop when searching in "package info screen" (Closes: #802648)

Long explanation because it took a long while to dig all this info and
understand the problem, and if this is recorded it can help to explain many
of the problems and circumstances that concur.

When the widget in focus is large (mostly a package with a very long
description that is larger than the screen; and the view is completely
filled by this description and doesn't there are no other tree nodes in
focus --like the main package name at the top, or Depends or others in the
bottom--), then a search which doesn't lead to other elements of the tree
enters in an endless loop.

As the original report explains, this is triggered for example with the
package "youtube-dl" which contains a long description with many of the
websites that it supports, in the "package info screen", and when the scroll
is moved 1 line down, so the only thing visible (even in a moderately large
screen) is part of this description.  When typing "/" to start search and
then "you", the page starts to jump for the incremental search (matching for
example the first version of the package that appears as node under
"Versions of youtube-dl"), but then if a further "k" is typed, as the
original reported did (presumably to verify if the program supported sites
named "youku" and "youku:show" that appear in the description), it doesn't
match any other node in the tree and it entered an endless loop.  The code
does not support search within this kind of special node, which it could do;
but failing that what it should happen instead is that, in the absence of
matches, it goes back to the original view.

The reason why this happens is not fully understood, the code is messy and
difficult to grok.  It seems that the loops expect to stop when either
there's a match or when "curr == start" (so it went through all elems and
didn't find a match), but this never ends up happening, either because the
iteration (which involves C++ operators and iterators traversing either
hierarchical or flat version of the tree) doesn't really go through all of
the nodes or because they are not considered because they are "out of view".

The node where the description appears is not a regular node of the tree, it
is one bolted with many package related fields like Description and
Homepage, but different from the rest of the nodes of the tree which are
only package names, versions, dependencies and so on.  The code was clearly
designed with these simpler nodes in mind, and the node with the Description
is clearly an abuse of the concept.

So basically the best solution found to avoid the endless loop was to just
stop when the loop goes through "end" for second time, if there were no
matches.  It's not optimal, but acceptable in terms of performance,
specially having into account that it's not an operation performed in tight
loops and the difference is not noticeable with other searches.

A proper solution would mean to really redesign both cwidget and packages
using it like aptitude so the info page is not designed as a tree and then
riding one of the nodes with all sorts of extra information which is not
searchable.


Cheers.
--
Manuel A. Fernandez Montecelo 

Bug#802648: [Aptitude-devel] Bug#802648: aptitude: definite loop when searching "youk" in "youtube-dl" package info page

[Manuel A. Fernandez Montecelo]

Control: reassign -1 src:cwidget


Hi,

2015-10-26 10:33 Manuel A. Fernandez Montecelo:

Control: found -1 aptitude/0.6.11


Hi all,

2015-10-22 12:23 Axel Beckert:

Control: tag -1 + confimred - unreproducible

Hi,

Axel Beckert wrote:

> 5. press "/", and enter "you", everything is OK for now
> 6. enter "k", the definite loop occures

JFTR: I can't reproduce this with 0.7.2-1 from Debian Testing (in the
big terminal). Will test Sid later.


Tried it on Debian Sid amd64 with a 157x21 terminal. But nothing
crashed, continues to work fine.


Sorry, I think I misunderstood the description initially. I
interpreted 'enter "you"' as typing the letters "y", "o", "u", and
then pressing the enter key and the pressing "k" to get one line up.

But if you enter "youk" aptitude no more reacts except on Ctrl-C. At
least once in the 157x21 terminal. But I wasn't able to reproduce it
even in the 157x21 terminal after I tried it in the same process while
the terminal was bigger.

So it may depend on what has already been done (and hence maybe cached
internally) before.

I was not able to reproduce it in 0.7.2-1 from testing at all, even
if I followed the instructions inside a freshly started aptitude in a
157x21 terminal.


I can reproduce it all the time, also in 0.6.11 from stable (Jessie).

I think that it's partly due to the incremental search feature
(according to the backtrace), feature about which there are more
complaints in the BTS (but I haven't checked if they are related or
not).


I've been investigating this again and I believe that it's actually a
problem with the cwidget library, that has happened since forever.

This happens also for example with devscripts and rhythmbox-plugins,
which have a long description which makes the main/first subtree (the
one with the package name, the second subtree is "Depends") to also
"fill" my terminal (expand more than a screenful vertically), like
youtube-dl.  It doesn't happen with libwiretap5 even if the description
is quite long, for example.

I think that it has to do with how the cwidget implementation moves the
view to jump to where the term being searched appears, and that gets
confused when the contents are off the screen or something similar.  The
backtrace points to line 854 in ./src/cwidget/widgets/tree.cc with the
line:

 while(curr!=start && !matches(*curr))

and with aptitude's menu_tree.cc, line 82. 



Searching for "yo" in "youtube-dl" screen doesn't produce the desired
effect (I presume), of searching e.g. inside the Description field.

When the screen starts at line "zero" [1], with incsearch enabled, "y"
jumps to the line below [2], after "yo" jumps to the last line (below
[3]), after "you" the same (and at this point it didn't hang yet, one
can delete with backspace etc).  With "youk" enters the infinite loop.

If one presses "yok", or "youk", it also triggers the
infinite loop.

It will need quite some debugging, and probably a new cwidget release to
get this fixed.


[1] That is, printing:
   i--\ youtube-dl2016.02.22-1   2016.02.22-1

[2]
   --\ Depends (3)
 --\ python-pkg-resources

[3]
   --- Packages which depend on youtube-dl (5)
  --\ Versions of youtube-dl (1)
   
--

Manuel A. Fernandez Montecelo 

Bug#802648: [Aptitude-devel] Bug#802648: aptitude: definite loop when searching "youk" in "youtube-dl" package info page

[Manuel A. Fernandez Montecelo]

Control: found -1 aptitude/0.6.11


Hi all,

2015-10-22 12:23 Axel Beckert:

Control: tag -1 + confimred - unreproducible

Hi,

Axel Beckert wrote:

> > 5. press "/", and enter "you", everything is OK for now
> > 6. enter "k", the definite loop occures
>
> JFTR: I can't reproduce this with 0.7.2-1 from Debian Testing (in the
> big terminal). Will test Sid later.

Tried it on Debian Sid amd64 with a 157x21 terminal. But nothing
crashed, continues to work fine.


Sorry, I think I misunderstood the description initially. I
interpreted 'enter "you"' as typing the letters "y", "o", "u", and
then pressing the enter key and the pressing "k" to get one line up.

But if you enter "youk" aptitude no more reacts except on Ctrl-C. At
least once in the 157x21 terminal. But I wasn't able to reproduce it
even in the 157x21 terminal after I tried it in the same process while
the terminal was bigger.

So it may depend on what has already been done (and hence maybe cached
internally) before.

I was not able to reproduce it in 0.7.2-1 from testing at all, even
if I followed the instructions inside a freshly started aptitude in a
157x21 terminal.


I can reproduce it all the time, also in 0.6.11 from stable (Jessie).

I think that it's partly due to the incremental search feature
(according to the backtrace), feature about which there are more
complaints in the BTS (but I haven't checked if they are related or
not).


Cheers.
--
Manuel A. Fernandez Montecelo 

Bug#802648: [Aptitude-devel] Bug#802648: aptitude: definite loop when searching "youk" in "youtube-dl" package info page

[Axel Beckert]

Control: notfound -1 aptitude/0.6.11
Control: found -1 aptitude/0.6.11-1

Hi,

Manuel A. Fernandez Montecelo wrote:
> I think that it's partly due to the incremental search feature
> (according to the backtrace), feature about which there are more
> complaints in the BTS (but I haven't checked if they are related or
> not).

That explains why I wasn't able to reproduce it most of the time. I
always have incremental search disabled. I consider it quite annoying,
at least in this case.

Which makes me wonder why I was able to reproduce it at least once...

Regards, Axel
-- 
 ,''`.  |  Axel Beckert , http://people.debian.org/~abe/
: :' :  |  Debian Developer, ftp.ch.debian.org Admin
`. `'   |  4096R: 2517 B724 C5F6 CA99 5329  6E61 2FF9 CD59 6126 16B5
  `-|  1024D: F067 EA27 26B9 C3FC 1486  202E C09E 1D89 9593 0EDE

Bug#802648: [Aptitude-devel] Bug#802648: aptitude: definite loop when searching "youk" in "youtube-dl" package info page

[Manuel A. Fernandez Montecelo]

2015-10-26 12:25 Axel Beckert:

Control: notfound -1 aptitude/0.6.11
Control: found -1 aptitude/0.6.11-1

Hi,

Manuel A. Fernandez Montecelo wrote:

I think that it's partly due to the incremental search feature
(according to the backtrace), feature about which there are more
complaints in the BTS (but I haven't checked if they are related or
not).


That explains why I wasn't able to reproduce it most of the time. I
always have incremental search disabled. I consider it quite annoying,
at least in this case.

Which makes me wonder why I was able to reproduce it at least once...


Useful to know.  In that case maybe it's not related, or happens in both
cases (incremental and not incremental).


--
Manuel A. Fernandez Montecelo 

Bug#802648: [Aptitude-devel] Bug#802648: aptitude: definite loop when searching "youk" in "youtube-dl" package info page

[Axel Beckert]

Hi,

thanks for the bug report.

Zhang Jingqiang wrote:
> Step to reproduce:
> 1. run "aptitude"
> 2. press "/", and enter "youtube-dl", press Enter
> 3. press Enter, youtube-dl info page show up
> 4. Press "PgDn", so now the first line is "Descripition: ..."

I think you meant "cursor down" here. (Then again, that depends a lot
on the terminal size. I had a quite large terminal, 119x66. Will try
with a smaller terminal later. :-)

> 5. press "/", and enter "you", everything is OK for now
> 6. enter "k", the definite loop occures

JFTR: I can't reproduce this with 0.7.2-1 from Debian Testing (in the
big terminal). Will test Sid later.

Regards, Axel
-- 
 ,''`.  |  Axel Beckert , http://people.debian.org/~abe/
: :' :  |  Debian Developer, ftp.ch.debian.org Admin
`. `'   |  4096R: 2517 B724 C5F6 CA99 5329  6E61 2FF9 CD59 6126 16B5
  `-|  1024D: F067 EA27 26B9 C3FC 1486  202E C09E 1D89 9593 0EDE

Bug#802648: [Aptitude-devel] Bug#802648: aptitude: definite loop when searching "youk" in "youtube-dl" package info page

[Axel Beckert]

Control: tag -1 + confimred - unreproducible

Hi,

Axel Beckert wrote:
> > > 5. press "/", and enter "you", everything is OK for now
> > > 6. enter "k", the definite loop occures
> > 
> > JFTR: I can't reproduce this with 0.7.2-1 from Debian Testing (in the
> > big terminal). Will test Sid later.
> 
> Tried it on Debian Sid amd64 with a 157x21 terminal. But nothing
> crashed, continues to work fine.

Sorry, I think I misunderstood the description initially. I
interpreted 'enter "you"' as typing the letters "y", "o", "u", and
then pressing the enter key and the pressing "k" to get one line up.

But if you enter "youk" aptitude no more reacts except on Ctrl-C. At
least once in the 157x21 terminal. But I wasn't able to reproduce it
even in the 157x21 terminal after I tried it in the same process while
the terminal was bigger.

So it may depend on what has already been done (and hence maybe cached
internally) before.

I was not able to reproduce it in 0.7.2-1 from testing at all, even
if I followed the instructions inside a freshly started aptitude in a
157x21 terminal.

Regards, Axel
-- 
 ,''`.  |  Axel Beckert , http://people.debian.org/~abe/
: :' :  |  Debian Developer, ftp.ch.debian.org Admin
`. `'   |  4096R: 2517 B724 C5F6 CA99 5329  6E61 2FF9 CD59 6126 16B5
  `-|  1024D: F067 EA27 26B9 C3FC 1486  202E C09E 1D89 9593 0EDE

Bug#802648: [Aptitude-devel] Bug#802648: aptitude: definite loop when searching "youk" in "youtube-dl" package info page

[Axel Beckert]

Control: tag -1 + unreproducible

Hi again,

Axel Beckert wrote:
> Zhang Jingqiang wrote:
> > Step to reproduce:
> > 1. run "aptitude"
> > 2. press "/", and enter "youtube-dl", press Enter
> > 3. press Enter, youtube-dl info page show up
> > 4. Press "PgDn", so now the first line is "Descripition: ..."
> 
> I think you meant "cursor down" here. (Then again, that depends a lot
> on the terminal size. I had a quite large terminal, 119x66. Will try
> with a smaller terminal later. :-)
> 
> > 5. press "/", and enter "you", everything is OK for now
> > 6. enter "k", the definite loop occures
> 
> JFTR: I can't reproduce this with 0.7.2-1 from Debian Testing (in the
> big terminal). Will test Sid later.

Tried it on Debian Sid amd64 with a 157x21 terminal. But nothing
crashed, continues to work fine.

Regards, Axel
-- 
 ,''`.  |  Axel Beckert , http://people.debian.org/~abe/
: :' :  |  Debian Developer, ftp.ch.debian.org Admin
`. `'   |  4096R: 2517 B724 C5F6 CA99 5329  6E61 2FF9 CD59 6126 16B5
  `-|  1024D: F067 EA27 26B9 C3FC 1486  202E C09E 1D89 9593 0EDE