[Bug 12701] New: listview: works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

Summary: listview: works slow and wrong
           Product: Wine
           Version: 0.9.60
          Platform: PC
        OS/Version: Linux
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: comctl32
        AssignedTo: [e-mail]
        ReportedBy: [e-mail]

Created an attachment (id=12353)
 --> (http://bugs.winehq.org/attachment.cgi?id=12353)
7zipped log of warn+all,+listview on wine 0.9.60

Here is a deal: There is a list view containing 300K+ items. Looks like this:
http://polosatus.ru/wine/listview.png It's a full list of all words indexed in
some database.

When using native comctl32.dll, you just type the text in and the list
*immediately* jumps to the item that starts from the letters you've entered.
Works pretty simple and swift and no CPU load.

But when you use builtin comctl32.dll there are 3 problems:

1. It hangs on each keypress. In log (77Mb) you may see a lot of iterations
like this:

trace:listview:ranges_cmp range1=[22765, 22766], range2=[25271, 25272], cmp=-1
trace:listview:ranges_contain (nItem=22766)
trace:listview:ranges_assert *** Checking ranges_contain:2691:before contain
***
trace:listview:ranges_dump    [25271, 25272]
trace:listview:ranges_assert --- Done checking---

And each keypress results in new rescan, as it hangs pretty well even if the
highlighted item matches new typed letter. And the further first match is, the
longer it hangs on each keypress.

2. It searches not items STARTING with enterred text, but items CONTAINING it.
Both of these bugs make usage of this box a nonsense. When you try to find, for
instance an item "most" and you type "most" it would stop at the point "almost"
and so, you have to search it manually by scrolling.

3. When I close this box, it just hangs again for a few secs (and generates
another 50M+ to log).

When generating log, I've typed only three letters: "alt" and it was enough to
generate 20M+ log. Another 55M+ where generated when I clicked close button.

[Bug 12701] listview: works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

--- Comment #1 from Austin English   2008-04-20 18:22:13 ---
What application is this?

[Bug 12701] listview: works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

Reece Dunn  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |[e-mail]

--- Comment #2 from Reece Dunn   2008-04-20 18:24:47 ---
Looks like it should be straightforward to implement a testcase for item 2, and
a stress/performance test could be setup for item 1 that would just be a test
case that adds lots of similar items (e.g. from a dictionary).

It would be useful to find out if this is a standard or virtual listview, as
virtual listviews should perform better. Also, is it known whether the listview
is sorted or not?

All these combinations should be tested though, so they behave correctly.

[Bug 12701] listview: works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

--- Comment #3 from Igor Tarasov   2008-04-20 20:28:29 ---
(In reply to comment #1)
> What application is this?

Well, there is a link above (Show Apps affected by this bug). This is
Watchtower Library, non-redistributable software, so mentioning it here won't
help.

(In reply to comment #2)
> It would be useful to find out if this is a standard or virtual listview, as
> virtual listviews should perform better. Also, is it known whether the listview
> is sorted or not?

How can I figure that out?

As good as I understand, it just contains initially sorted list from database
index, and it does not sort the data itself.

[Bug 12701] listview: works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

nille  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1

--- Comment #4 from nille   2008-04-21 05:21:26 ---
*** This bug has been confirmed by popular vote. ***

[Bug 12701] listview: works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

Dripple  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |[e-mail]

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

Lei Zhang  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|listview: works slow and    |watchtower library -
                   |wrong                       |listview works slow and
                   |                            |wrong

--- Comment #5 from Lei Zhang   2008-06-13 14:52:59 ---
trace:listview:LISTVIEW_Refresh ... Style=0x5003100d
trace:listview:LISTVIEW_Refresh ... Style=0x50035009

It's a virtual listview.

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

--- Comment #6 from Igor Tarasov   2008-06-13 16:21:38 ---
And what does that mean?

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

--- Comment #7 from Igor Tarasov   2008-10-13 09:34:12 ---
Another bug that I have discovered in this control is that it has some problems
in case-insensitive search. That is, when native comctl32.dll is used you may
enter text in any case you want, it still searches well. But when using wine
built-in library, search becomes case-sensitive.

So, this is still a problem in wine-1.1.6.

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

DrkShadow  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |winehq.10.drkshadow@spamgour
                   |                            |met.com

--- Comment #8 from DrkShadow   2009-01-29 23:05:26 ---
Looking at Wine 1.1.13, listview.c, LISTVIEW_ProcessLetterKeys...

At line 1593 is a call to lstrncmpiW -- the first param is the item name, the
second param is the search text, so

1. the search is always case insensitive
2. the search always begins at the front of the item name

However, it seems like large lists will still have a problem searching. Usually
I see this in file selection dialogs where it searches and then must redraw the
listview with icons. At line 1549 ListView sets the lastKeyPressTimestamp. It
then performs the search. Only 450ms are allowed between keypresses, so if the
search isn't finished in under half a second before the second key can be
processed, the listview will cancel the search and restart a new search with
only the second typed character.

I propose fixing this by duplicating the line at 1549; at line 1604, insert:
/* Update time count _after_ search in case search was slow */
infoPtr->lastKeyPressTimestamp = GetTickCount();

thus, the second key press time is measured _after_ the search ( and event
processing) is complete, and if the search takes excessively long, it won't
affect the second keypress.

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

--- Comment #9 from Igor Tarasov   2009-01-31 10:34:49 ---
Created an attachment (id=19125)
 --> (http://bugs.winehq.org/attachment.cgi?id=19125)
test patch

I think I've discovered all the bugs:

1. Wrong filtering and case-senisveness:

I've found out that ours listview calls LVM_FINDITEMW and in listview.c:5145 we
see this:

if (lpFindInfo->flags & LVFI_PARTIAL)
            {
                if (strstrW(lvItem.pszText, lpFindInfo->psz) == NULL) continue;
            }
            else
            {
                if (lstrcmpW(lvItem.pszText, lpFindInfo->psz) != 0) continue;
            }

Well, both of these calls (strstrW and lstrcmpW) are case-sensitive. While MSDN
states that search is supposed to be case-insensitive:
http://msdn.microsoft.com/en-us/library/bb774745(VS.85).aspx

Here are the roots of the first part of this bug. Second part of our bug is
about searching not items starting with, but items containing text.
LVFI_PARTIAL means that we should look not for items containing text, but for
items starting with it.

Here is my version (attached as patch):

if (lpFindInfo->flags & LVFI_PARTIAL)
            {
                const WCHAR *str1 = lvItem.pszText;
                const WCHAR *str2 = lpFindInfo->psz;

if (*str2) {
                    while (*str2 && *str1)
                    {
                        if (tolowerW(*str1) != tolowerW(*str2)) break;
                        str1++;
                        str2++;
                    }
                    if (*str2)
                        continue;
                }
            }
            else
            {
                if (lstrcmpiW(lvItem.pszText, lpFindInfo->psz) != 0) continue;
            }

This works as expected, though I am not sure as if this is the best (and
fastest) way to do this.

2. Selection works slow. For every item in our listview during the search
LISTVIEW_GetItemT is being called (which is quite heavy for such big cycle).
This function, on it's part, sends LVN_GETDISPINFOW notification (line 5487).
So, several thousands of notifications take some time ;) Notice the comment at
line 5472:

/* apparently, we should not callback for lParam in LVS_OWNERDATA */

Debug lines show that the fields we need (pszText) are available BEFORE sending
that message. Maybe, this could be avoided or worked out?

3. Slowdown when closing listview window. Slow place is function
LISTVIEW_DeleteAllItems. MSDN states: LVM_DELETEALLITEMS Sets the item count to
zero and clears all internal selection variables, but it does not actually
delete any items. It makes a notification callback.
http://msdn.microsoft.com/en-us/library/bb774735(VS.85).aspx

However, code on line 4512 does a lot more than required (also sending
notifications for each listview item). As good as I understand only 1
notification is required. And deletion could be done via ranges_destroy.

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

Austin English  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch

--- Comment #10 from Austin English   2009-01-31 14:38:37 ---
Testcases are always good.

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

--- Comment #11 from DrkShadow   2009-02-01 02:05:54 ---
Created an attachment (id=19142)
 --> (http://bugs.winehq.org/attachment.cgi?id=19142)
Part 1: case insensitive and match-anywhere search

Case sensitivity fixed. The matching on a partial word should be fixed. Could
you test this with what you have? I don't know of anything else that searches
in this way.. will look at the other two issues later.

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

--- Comment #12 from Igor Tarasov   2009-02-01 08:34:11 ---
The patch works, but kinda weird. It searches when I type "a", "ab", but when I
add "r" it cant find anything, while there are dozen of words starting with
"abr" in the list. I just don't understand how is this possible.

And typing letters quickly does not help. Sometimes it helps (maximim 2 letters
at once), but generally it makes full search for each typed in letter (if you
type 3 letters quickly it does 3 full searches).

And regarding slowdowns. I was curious, does native comctl32 fetches each item
in cycle via notification when searching. So, I've installed native comctl32
and made a test run generating +message log. I've launched the application,
opened that listview, entered couple of letters, closed it. With native comctl
log size was ~4,5 Mb.

So, I did the same with builtin version. The final log was 360+Mb. It's clear
that virtual listview should not send that crazy amount of messages. BTW, most
part of that log (over 300+) was generated after I closed that listview.

That means that I was right, now we have to avoid that it virtual listviews
will get quick.

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

Igor Tarasov  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #19125|0                           |1
        is obsolete|                            |

--- Comment #13 from Igor Tarasov   2009-02-17 06:37:09 ---
Created an attachment (id=19512)
 --> (http://bugs.winehq.org/attachment.cgi?id=19512)
Cumulative patch

Okay, I think I've figured everything out and this patch fixes all wrong
behavour:

1. Slowdown when destroying virtual listview: the problem as I've said earlier
was that listview_deleteall was issuing notification for each element (which
should not be done, according to MSDN). So, I've moved sending that
notification in if block and now notifications are being sent only for not
virtual listviews. Result: the listview is being destroyed instantly. Just as
with native comctl32.

2. Slow search. As I've found in MSDN here:
http://msdn.microsoft.com/en-us/library/bb774735(VS.85).aspx , listview control
should not search for virtual listviews. Instead, it should send LVN_ODFINDITEM
to the application. And guess what? It was unimplemented in wine. So, I've
added it. Result: search works instantly, as with native comctl.

3. But before that DrkShadow fixed incorrect behaviour of LISTVIEW_FindItemW.
This was also added to this patch.

So, now that listview warks perfectly as native comctl32.

I have just one question: I should send it to wine-patches in one patch, or in
2-3?

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

--- Comment #14 from Igor Tarasov   2009-02-19 10:10:53 ---
The patches have been comitted:

http://www.winehq.org/pipermail/wine-cvs/2009-February/053240.html
http://www.winehq.org/pipermail/wine-cvs/2009-February/053241.html

It fixes virtual listview behaviour completely, and fixes this bug. But, as for
not virtual listviews they still behave buggy. And there is a patch, that
mostly was written by DrkShadow, and is present in patch from previous post. I
have not submitted it only because the patch was written not by me, but
DrkShadow has not been responding my emails.

What should I do?

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

Dan Kegel  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |[e-mail]

--- Comment #15 from Dan Kegel   2009-02-19 10:32:43 ---
He's using a spamblocking service, so your emails may not be
getting through.  Google his address... http://www.hainei.us/view-274286.html
seems to be related.

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

--- Comment #16 from Austin English   2009-02-19 11:42:39 ---
(In reply to comment #14)
> The patches have been comitted:
>
> http://www.winehq.org/pipermail/wine-cvs/2009-February/053240.html
> http://www.winehq.org/pipermail/wine-cvs/2009-February/053241.html
>
> It fixes virtual listview behaviour completely, and fixes this bug. But, as for
> not virtual listviews they still behave buggy. And there is a patch, that
> mostly was written by DrkShadow, and is present in patch from previous post. I
> have not submitted it only because the patch was written not by me, but
> DrkShadow has not been responding my emails.
>
> What should I do?

Could mark this bug fixed and file a new one, or submit the bug under his
name/e-mail.

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

Igor Tarasov  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED

--- Comment #17 from Igor Tarasov   2009-02-19 15:13:29 ---
I have his real email, we've been discussing this bug. So, I've sent him a
message again, I'll wait some time and then do something.

Meanwhile, I mark this bug as fixed.

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

--- Comment #18 from Dan Kegel   2009-02-19 15:15:09 ---
Note that to get a patch accepted, he'll have to use his real name.

[Bug 12701] watchtower library - listview works slow and wrong

http://bugs.winehq.org/show_bug.cgi?id=12701

Alexandre Julliard  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |CLOSED

--- Comment #19 from Alexandre Julliard   2009-02-27 16:31:00 ---
Closing bugs fixed in 1.1.16.

[Bug 12701] watchtower library - listview works slow and wrong

https://bugs.winehq.org/show_bug.cgi?id=12701

Anastasius Focht  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
      Fixed by SHA1|                            |d86a5a611de6df1c5dfcfa476ec
                   |                            |752b0648a4e52
                 CC|                            |[e-mail]