[PATCH v2 1/4] shell32/autocomplete: Implement a cache and sort the enumerated strings for proper behavior

[Gabriel Ivăncescu]

Windows doesn't reset and re-enumerate it everytime autocompletion happens,
and it also sorts the strings. This matches it more closely and makes it
more useable on large lists as well.

Signed-off-by: Gabriel Ivăncescu 
---

v2: Merged the first 3 patches, used qsort, replaced goto that broke out
of nested scope with a BOOL check, and moved the goto failure path at the
end outside of any blocks.

dlls/shell32/autocomplete.c | 288 +++++++++++++++++++++++++++++++++++---------
 1 file changed, 228 insertions(+), 60 deletions(-)

diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c
index dfe7638..751bda0 100644
--- a/dlls/shell32/autocomplete.c
+++ b/dlls/shell32/autocomplete.c
@@ -25,7 +25,6 @@
   - implement ACO_FILTERPREFIXES style
   - implement ACO_RTLREADING style
   - implement ResetEnumerator
-  - string compares should be case-insensitive, the content of the list should be sorted

*/
 #include "config.h"
@@ -62,6 +61,8 @@ typedef struct
     LONG ref;
     BOOL initialized;
     BOOL enabled;
+    UINT enum_strs_num;
+    WCHAR **enum_strs;
     HWND hwndEdit;
     HWND hwndListBox;
     WNDPROC wpOrigEditProc;
@@ -103,10 +104,160 @@ static void set_text_and_selection(IAutoCompleteImpl *ac, HWND hwnd, WCHAR *text
         CallWindowProcW(proc, hwnd, EM_SETSEL, start, end);
 }

+static int enumerate_strings_cmpfn(const void *a, const void *b)
+{
+    return strcmpiW(*(WCHAR* const*)a, *(WCHAR* const*)b);
+}
+
+static void enumerate_strings(IAutoCompleteImpl *ac)
+{
+    /*
+       Enumerate all of the strings and sort them in the internal list. Rough summary:
+
+         - Enumerate the strings and place their addresses in a chain of blocks (stack-like)
+         - Copy the pointers from the blocks into a contiguous array/list
+         - Sort the contiguous array/list
+
+       We don't free the enumerated strings (except on error) to avoid needless
+       copies, until the next reset (or the object itself is destroyed)
+    */
+    struct
+    {
+        void *prev;
+        LPOLESTR str[1020];
+    } *prevblock, *curblock;
+
+    UINT i, cur, numstrs = 0;
+    LPOLESTR *strs;
+
+    prevblock = NULL;
+    for (;;)
+    {
+        LONG rem;
+        BOOL break_enum = FALSE;
+
+        if ((curblock = heap_alloc(sizeof(*curblock))) == NULL)
+        {
+            if (!prevblock)
+                return;
+            curblock = prevblock;
+            cur = ARRAY_SIZE(curblock->str);
+            goto fail_and_free_blocks;
+        }
+        curblock->prev = prevblock;
+        rem = ARRAY_SIZE(curblock->str);
+
+        while (rem > 0)
+        {
+            ULONG n = 0;
+            cur = ARRAY_SIZE(curblock->str) - rem;
+            IEnumString_Next(ac->enumstr, rem, &curblock->str[cur], &n);
+            if (n == 0)
+            {
+                break_enum = TRUE;
+                break;
+            }
+            rem -= n;
+        }
+        if (break_enum) break;
+        prevblock = curblock;
+        numstrs += ARRAY_SIZE(curblock->str);
+    }
+
+    /* Allocate even if there were zero strings enumerated, to mark it non-NULL */
+    numstrs += cur;
+    if ((strs = heap_alloc(numstrs * sizeof(*strs))))
+    {
+        if (numstrs == 0)
+        {
+            ac->enum_strs = strs;
+            ac->enum_strs_num = numstrs;
+            heap_free(curblock);
+            return;
+        }
+
+        /* Copy the pointers from the chain of blocks to the contiguous list */
+        i = numstrs;
+        do
+        {
+            i -= cur;
+            memcpy(&strs[i], curblock->str, cur * sizeof(*strs));
+
+            prevblock = curblock->prev;
+            heap_free(curblock);
+            curblock = prevblock;
+            cur = ARRAY_SIZE(curblock->str);
+        } while (curblock);
+
+        /* Now sort the list */
+        qsort(strs, numstrs, sizeof(*strs), enumerate_strings_cmpfn);
+
+        ac->enum_strs = strs;
+        ac->enum_strs_num = numstrs;
+        return;
+    }
+
+fail_and_free_blocks:
+    do
+    {
+        LPOLESTR *str = curblock->str;
+        while (cur--)
+            CoTaskMemFree(str[cur]);
+        prevblock = curblock->prev;
+        heap_free(curblock);
+        curblock = prevblock;
+        cur = ARRAY_SIZE(curblock->str);
+    } while (curblock);
+}
+
+static UINT find_first_matching_enum_str(IAutoCompleteImpl *ac, WCHAR *text, UINT len)
+{
+    WCHAR **strs = ac->enum_strs;
+    UINT index = ~0, a = 0, b = ac->enum_strs_num;
+    while (a < b)
+    {
+        UINT i = (a + b - 1) / 2;
+        int cmp = strncmpiW(text, strs[i], len);
+        if (cmp == 0) index = i;
+        if (cmp <= 0) b = i;
+        else          a = i + 1;
+    }
+    return index;
+}
+
+static void free_enum_strs(IAutoCompleteImpl *ac)
+{
+    WCHAR **strs = ac->enum_strs;
+    if (strs)
+    {
+        UINT i = ac->enum_strs_num;
+        ac->enum_strs = NULL;
+        while (i--)
+            CoTaskMemFree(strs[i]);
+        heap_free(strs);
+    }
+}
+
 static void hide_listbox(IAutoCompleteImpl *ac, HWND hwnd)
 {
     ShowWindow(hwnd, SW_HIDE);
     SendMessageW(hwnd, LB_RESETCONTENT, 0, 0);
+    free_enum_strs(ac);
+}
+
+static void show_listbox(IAutoCompleteImpl *ac, UINT cnt)
+{
+    RECT r;
+    UINT width, height;
+
+    GetWindowRect(ac->hwndEdit, &r);
+    SendMessageW(ac->hwndListBox, LB_CARETOFF, 0, 0);
+
+    /* Windows XP displays 7 lines at most, then it uses a scroll bar */
+    height = SendMessageW(ac->hwndListBox, LB_GETITEMHEIGHT, 0, 0) * min(cnt + 1, 7);
+    width = r.right - r.left;
+
+    SetWindowPos(ac->hwndListBox, HWND_TOP, r.left, r.bottom + 1, width, height, SWP_SHOWWINDOW);
 }

static size_t format_quick_complete(WCHAR *dst, const WCHAR *qc, const WCHAR *str, size_t str_len)
@@ -225,7 +376,11 @@ static LRESULT change_selection(IAutoCompleteImpl *ac, HWND hwnd, UINT key)

static BOOL do_aclist_expand(IAutoCompleteImpl *ac, WCHAR *txt, WCHAR *last_delim)
 {
-    WCHAR c = last_delim[1];
+    WCHAR c;
+    free_enum_strs(ac);
+    IEnumString_Reset(ac->enumstr);  /* call before expand */
+
+    c = last_delim[1];
     last_delim[1] = '\0';
     IACList_Expand(ac->aclist, txt);
     last_delim[1] = c;
@@ -261,6 +416,9 @@ static BOOL aclist_expand(IAutoCompleteImpl *ac, WCHAR *txt)
         while (i--)
             if (strchrW(delims, txt[i]))
                 return do_aclist_expand(ac, txt, &txt[i]);
+
+        /* Windows doesn't expand without a delim, but it does reset */
+        free_enum_strs(ac);
     }

return FALSE;
@@ -293,11 +451,65 @@ static void autoappend_str(IAutoCompleteImpl *ac, WCHAR *text, UINT len, WCHAR *
         heap_free(tmp);
 }

+static BOOL display_matching_strs(IAutoCompleteImpl *ac, WCHAR *text, UINT len,
+                                  HWND hwnd, enum autoappend_flag flag)
+{
+    /* Return FALSE if we need to hide the listbox */
+    WCHAR **str = ac->enum_strs;
+    UINT cnt, a, b, i;
+    if (!str) return (ac->options & ACO_AUTOSUGGEST) ? FALSE : TRUE;
+
+    if (len)
+    {
+        i = find_first_matching_enum_str(ac, text, len);
+        if (i == ~0)
+            return (ac->options & ACO_AUTOSUGGEST) ? FALSE : TRUE;
+
+        if (flag == autoappend_flag_yes)
+            autoappend_str(ac, text, len, str[i], hwnd);
+        if (!(ac->options & ACO_AUTOSUGGEST))
+            return TRUE;
+
+        /* Find the last string that begins with text, starting the search from i,
+           which is guaranteed to find at least one string (if none other, then i) */
+        a = i, b = ac->enum_strs_num;
+        do
+        {
+            UINT mid = (a + b - 1) / 2u;
+            if (!strncmpiW(text, str[mid], len))
+                a = mid + 1;
+            else
+                b = mid;
+        } while (a < b);
+    }
+    else
+    {
+        if (!(ac->options & ACO_AUTOSUGGEST))
+            return TRUE;
+        i = 0;
+        a = ac->enum_strs_num;
+        if (a == 0)
+            return FALSE;
+    }
+    cnt = a - i;
+
+    SendMessageW(ac->hwndListBox, WM_SETREDRAW, FALSE, 0);
+    SendMessageW(ac->hwndListBox, LB_RESETCONTENT, 0, 0);
+    SendMessageW(ac->hwndListBox, LB_INITSTORAGE, cnt, 0);
+    do
+        SendMessageW(ac->hwndListBox, LB_INSERTSTRING, -1, (LPARAM)str[i]);
+    while (++i < a);
+
+    show_listbox(ac, cnt);
+    SendMessageW(ac->hwndListBox, WM_SETREDRAW, TRUE, 0);
+    return TRUE;
+}
+
 static void autocomplete_text(IAutoCompleteImpl *ac, HWND hwnd, enum autoappend_flag flag)
 {
-    HRESULT hr;
     WCHAR *text;
-    UINT cpt, size, len = SendMessageW(hwnd, WM_GETTEXTLENGTH, 0, 0);
+    BOOL expanded = FALSE;
+    UINT size, len = SendMessageW(hwnd, WM_GETTEXTLENGTH, 0, 0);

if (flag != autoappend_flag_displayempty && len == 0)
     {
@@ -313,79 +525,35 @@ static void autocomplete_text(IAutoCompleteImpl *ac, HWND hwnd, enum autoappend_
     if (len + 1 != size)
         text = heap_realloc(text, (len + 1) * sizeof(WCHAR));

-    /* Reset it here to simplify the logic in aclist_expand for
-       empty strings, since it tracks changes using txtbackup,
-       and Reset needs to be called before IACList::Expand */
-    IEnumString_Reset(ac->enumstr);
     if (ac->aclist)
     {
-        aclist_expand(ac, text);
         if (text[len - 1] == '\' || text[len - 1] == '/')
             flag = autoappend_flag_no;
+        expanded = aclist_expand(ac, text);
+    }
+    if (expanded || !ac->enum_strs)
+    {
+        if (!expanded) IEnumString_Reset(ac->enumstr);
+        enumerate_strings(ac);
     }

-    /* Set txtbackup to point to text itself (which must not be released) */
+    /* Set txtbackup to point to text itself (which must not be released),
+       and it must be done here since aclist_expand uses it to track changes */
     heap_free(ac->txtbackup);
     ac->txtbackup = text;

-    if (ac->options & ACO_AUTOSUGGEST)
+    if (!display_matching_strs(ac, text, len, hwnd, flag))
     {
-        SendMessageW(ac->hwndListBox, WM_SETREDRAW, FALSE, 0);
+        /* Hide the listbox, but do not clear the enum strs, to match Windows */
+        ShowWindow(ac->hwndListBox, SW_HIDE);
         SendMessageW(ac->hwndListBox, LB_RESETCONTENT, 0, 0);
     }
-    for (cpt = 0;;)
-    {
-        LPOLESTR strs = NULL;
-        ULONG fetched;
-
-        hr = IEnumString_Next(ac->enumstr, 1, &strs, &fetched);
-        if (hr != S_OK)
-            break;
-
-        if (!strncmpiW(text, strs, len))
-        {
-            if (cpt == 0 && flag == autoappend_flag_yes)
-            {
-                autoappend_str(ac, text, len, strs, hwnd);
-                if (!(ac->options & ACO_AUTOSUGGEST))
-                {
-                    CoTaskMemFree(strs);
-                    break;
-                }
-            }
-
-            if (ac->options & ACO_AUTOSUGGEST)
-                SendMessageW(ac->hwndListBox, LB_ADDSTRING, 0, (LPARAM)strs);
-
-            cpt++;
-        }
-
-        CoTaskMemFree(strs);
-    }
-
-    if (ac->options & ACO_AUTOSUGGEST)
-    {
-        if (cpt)
-        {
-            RECT r;
-            UINT height = SendMessageW(ac->hwndListBox, LB_GETITEMHEIGHT, 0, 0);
-            SendMessageW(ac->hwndListBox, LB_CARETOFF, 0, 0);
-            GetWindowRect(hwnd, &r);
-            /* It seems that Windows XP displays 7 lines at most
-               and otherwise displays a vertical scroll bar */
-            SetWindowPos(ac->hwndListBox, HWND_TOP,
-                         r.left, r.bottom + 1, r.right - r.left, height * min(cpt + 1, 7),
-                         SWP_SHOWWINDOW );
-            SendMessageW(ac->hwndListBox, WM_SETREDRAW, TRUE, 0);
-        }
-        else
-            hide_listbox(ac, ac->hwndListBox);
-    }
 }

static void destroy_autocomplete_object(IAutoCompleteImpl *ac)
 {
     ac->hwndEdit = NULL;
+    free_enum_strs(ac);
     if (ac->hwndListBox)
         DestroyWindow(ac->hwndListBox);
     IAutoComplete2_Release(&ac->IAutoComplete2_iface);

[PATCH v2 2/4] shell32/autocomplete: Don't reset the enumerator when losing focus if the edit control is still visible

[Gabriel Ivăncescu]

Signed-off-by: Gabriel Ivăncescu 
---
 dlls/shell32/autocomplete.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c
index 751bda0..0391f14 100644
--- a/dlls/shell32/autocomplete.c
+++ b/dlls/shell32/autocomplete.c
@@ -665,10 +665,15 @@ static LRESULT APIENTRY ACEditSubclassProc(HWND hwnd, UINT uMsg, WPARAM wParam,
                 hide_listbox(This, This->hwndListBox);
             return 0;
         case WM_KILLFOCUS:
-            if ((This->options & ACO_AUTOSUGGEST) && ((HWND)wParam != This->hwndListBox))
+            if (This->options & ACO_AUTOSUGGEST)
             {
-                hide_listbox(This, This->hwndListBox);
+                if ((HWND)wParam == This->hwndListBox) break;
+                ShowWindow(This->hwndListBox, SW_HIDE);
+                SendMessageW(This->hwndListBox, LB_RESETCONTENT, 0, 0);
             }
+
+            /* Reset the enumerator if it's not visible anymore */
+            if (!IsWindowVisible(hwnd)) free_enum_strs(This);
             break;
         case WM_KEYDOWN:
             return ACEditSubclassProc_KeyDown(This, hwnd, uMsg, wParam, lParam);

[PATCH v2 3/4] shell32/autocomplete: Reset the enumerator when the listbox is empty even when auto-suggest is disabled

[Gabriel Ivăncescu]

This is needed for auto-append only AutoComplete controls.

Signed-off-by: Gabriel Ivăncescu 
---
 dlls/shell32/autocomplete.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c
index 0391f14..dbcd725 100644
--- a/dlls/shell32/autocomplete.c
+++ b/dlls/shell32/autocomplete.c
@@ -515,6 +515,8 @@ static void autocomplete_text(IAutoCompleteImpl *ac, HWND hwnd, enum autoappend_
     {
         if (ac->options & ACO_AUTOSUGGEST)
             hide_listbox(ac, ac->hwndListBox);
+        else
+            free_enum_strs(ac);
         return;
     }

[PATCH v2 4/4] shell32/tests: Test the amount of enumerator resets for AutoComplete

[Gabriel Ivăncescu]

Signed-off-by: Gabriel Ivăncescu 
---
 dlls/shell32/tests/autocomplete.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/dlls/shell32/tests/autocomplete.c b/dlls/shell32/tests/autocomplete.c
index 66bd472..8265bf9 100644
--- a/dlls/shell32/tests/autocomplete.c
+++ b/dlls/shell32/tests/autocomplete.c
@@ -274,6 +274,7 @@ struct string_enumerator
     WCHAR **data;
     int data_len;
     int cur;
+    UINT num_resets;
     UINT num_expand;
     WCHAR last_expand[32];
 };
@@ -349,6 +350,7 @@ static HRESULT WINAPI string_enumerator_Reset(IEnumString *iface)
     struct string_enumerator *this = impl_from_IEnumString(iface);

this->cur = 0;
+    this->num_resets++;

return S_OK;
 }
@@ -456,6 +458,7 @@ static void test_aclist_expand(HWND hwnd_edit, void *enumerator)
     static WCHAR str2[] = {'t','e','s','t','\','f','o','o','\','b','a','r','\','b','a',0};
     static WCHAR str2a[] = {'t','e','s','t','\','f','o','o','\','b','a','r','\',0};
     static WCHAR str2b[] = {'t','e','s','t','\','f','o','o','\','b','a','r','\','b','a','z','_','b','b','q','\',0};
+    obj->num_resets = 0;

ok(obj->num_expand == 0, "Expected 0 expansions, got %u\n", obj->num_expand);
     SendMessageW(hwnd_edit, WM_SETTEXT, 0, (LPARAM)str1);
@@ -464,12 +467,14 @@ static void test_aclist_expand(HWND hwnd_edit, void *enumerator)
     dispatch_messages();
     ok(obj->num_expand == 1, "Expected 1 expansion, got %u\n", obj->num_expand);
     ok(lstrcmpW(obj->last_expand, str1a) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str1a), wine_dbgstr_w(obj->last_expand));
+    ok(obj->num_resets == 1, "Expected 1 reset, got %u\n", obj->num_resets);
     SendMessageW(hwnd_edit, WM_SETTEXT, 0, (LPARAM)str2);
     SendMessageW(hwnd_edit, EM_SETSEL, ARRAY_SIZE(str2) - 1, ARRAY_SIZE(str2) - 1);
     SendMessageW(hwnd_edit, WM_CHAR, 'z', 1);
     dispatch_messages();
     ok(obj->num_expand == 2, "Expected 2 expansions, got %u\n", obj->num_expand);
     ok(lstrcmpW(obj->last_expand, str2a) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str2a), wine_dbgstr_w(obj->last_expand));
+    ok(obj->num_resets == 2, "Expected 2 resets, got %u\n", obj->num_resets);
     SetFocus(hwnd_edit);
     SendMessageW(hwnd_edit, WM_CHAR, '_', 1);
     SendMessageW(hwnd_edit, WM_CHAR, 'b', 1);
@@ -479,20 +484,24 @@ static void test_aclist_expand(HWND hwnd_edit, void *enumerator)
     SendMessageW(hwnd_edit, WM_CHAR, 'q', 1);
     dispatch_messages();
     ok(obj->num_expand == 2, "Expected 2 expansions, got %u\n", obj->num_expand);
+    ok(obj->num_resets == 2, "Expected 2 resets, got %u\n", obj->num_resets);
     SendMessageW(hwnd_edit, WM_CHAR, '\', 1);
     dispatch_messages();
     ok(obj->num_expand == 3, "Expected 3 expansions, got %u\n", obj->num_expand);
     ok(lstrcmpW(obj->last_expand, str2b) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str2b), wine_dbgstr_w(obj->last_expand));
+    ok(obj->num_resets == 3, "Expected 3 resets, got %u\n", obj->num_resets);
     SendMessageW(hwnd_edit, EM_SETSEL, ARRAY_SIZE(str1a) - 1, -1);
     SendMessageW(hwnd_edit, WM_CHAR, 'x', 1);
     SendMessageW(hwnd_edit, WM_CHAR, 'y', 1);
     dispatch_messages();
     ok(obj->num_expand == 4, "Expected 4 expansions, got %u\n", obj->num_expand);
     ok(lstrcmpW(obj->last_expand, str1a) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str1a), wine_dbgstr_w(obj->last_expand));
+    ok(obj->num_resets == 4, "Expected 4 resets, got %u\n", obj->num_resets);
     SendMessageW(hwnd_edit, EM_SETSEL, ARRAY_SIZE(str1) - 1, -1);
     SendMessageW(hwnd_edit, WM_CHAR, 'x', 1);
     dispatch_messages();
     ok(obj->num_expand == 4, "Expected 4 expansions, got %u\n", obj->num_expand);
+    ok(obj->num_resets == 5, "Expected 5 resets, got %u\n", obj->num_resets);
 }

static void test_custom_source(void)
@@ -502,6 +511,7 @@ static void test_custom_source(void)
     static WCHAR str_beta[] = {'a','u','t','o',' ','c','o','m','p','l','e','t','e',0};
     static WCHAR str_au[] = {'a','u',0};
     static WCHAR *suggestions[] = { str_alpha, str_alpha2, str_beta };
+    struct string_enumerator *obj;
     IUnknown *enumerator;
     IAutoComplete2 *autocomplete;
     HWND hwnd_edit;
@@ -516,6 +526,7 @@ static void test_custom_source(void)
     ok(hr == S_OK, "CoCreateInstance failed: %x\n", hr);

string_enumerator_create((void**)&enumerator, suggestions, ARRAY_SIZE(suggestions));
+    obj = (struct string_enumerator*)enumerator;

hr = IAutoComplete2_SetOptions(autocomplete, ACO_AUTOSUGGEST | ACO_AUTOAPPEND);
     ok(hr == S_OK, "IAutoComplete2_SetOptions failed: %x\n", hr);
@@ -528,11 +539,14 @@ static void test_custom_source(void)
     dispatch_messages();
     SendMessageW(hwnd_edit, WM_GETTEXT, ARRAY_SIZE(buffer), (LPARAM)buffer);
     ok(lstrcmpW(str_beta, buffer) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str_beta), wine_dbgstr_w(buffer));
+    ok(obj->num_resets == 1, "Expected 1 reset, got %u\n", obj->num_resets);
     SendMessageW(hwnd_edit, EM_SETSEL, 0, -1);
     SendMessageW(hwnd_edit, WM_CHAR, '\b', 1);
     dispatch_messages();
     SendMessageW(hwnd_edit, WM_GETTEXT, ARRAY_SIZE(buffer), (LPARAM)buffer);
     ok(buffer[0] == '\0', "Expected empty string, got %s\n", wine_dbgstr_w(buffer));
+    ok(obj->num_resets == 1, "Expected 1 reset, got %u\n", obj->num_resets);
+    obj->num_resets = 0;

/* hijack the window procedure */
     HijackerWndProc_prev = (WNDPROC)SetWindowLongPtrW(hwnd_edit, GWLP_WNDPROC, (LONG_PTR)HijackerWndProc);
@@ -545,6 +559,7 @@ static void test_custom_source(void)
     dispatch_messages();
     SendMessageW(hwnd_edit, WM_GETTEXT, ARRAY_SIZE(buffer), (LPARAM)buffer);
     ok(lstrcmpW(str_au, buffer) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str_au), wine_dbgstr_w(buffer));
+    ok(obj->num_resets == 1, "Expected 1 reset, got %u\n", obj->num_resets);
     SendMessageW(hwnd_edit, EM_SETSEL, 0, -1);
     SendMessageW(hwnd_edit, WM_CHAR, '\b', 1);
     dispatch_messages();
@@ -558,6 +573,7 @@ static void test_custom_source(void)
     dispatch_messages();
     SendMessageW(hwnd_edit, WM_GETTEXT, ARRAY_SIZE(buffer), (LPARAM)buffer);
     ok(lstrcmpW(str_beta, buffer) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str_beta), wine_dbgstr_w(buffer));
+    ok(obj->num_resets == 2, "Expected 2 resets, got %u\n", obj->num_resets);
     /* end of hijacks */

test_aclist_expand(hwnd_edit, enumerator);

[PATCH v2 4/4] shell32/tests: Test the amount of enumerator resets for AutoComplete

[Marvin]

Hi,

While running your changed tests on Windows, I think I found new failures.
Being a bot and all I'm not very good at pattern recognition, so I might be
wrong, but could you please double-check?

Full results can be found at:
https://testbot.winehq.org/JobDetails.pl?Key=43485

Your paranoid android.

=== w864 (32 bit Windows report) ===

shell32:
autocomplete.c:468: Test failed: Expected 1 expansion, got 0

[PATCH v2 4/4] shell32/tests: Test the amount of enumerator resets for AutoComplete

[Gabriel Ivăncescu]

On Wed, Oct 24, 2018 at 10:14 PM Marvin  wrote:
> Hi,
>
> While running your changed tests on Windows, I think I found new failures.
> Being a bot and all I'm not very good at pattern recognition, so I might be
> wrong, but could you please double-check?
>
> Full results can be found at:
> https://testbot.winehq.org/JobDetails.pl?Key=43485
>
> Your paranoid android.
>
> === w864 (32 bit Windows report) ===
>
> shell32:
> autocomplete.c:468: Test failed: Expected 1 expansion, got 0

I have no idea how this failed right now but not before on this
version of Windows, this fail applies to the ACList::Expand tests, not
even touched by these patches.

The fact that it did not expand after a \ sounds like a bug to me.
It's not like there are any race conditions here, even used
dispatch_messages() before it just in case.

So I think it can be ignored.

[Huw Davies]

On Wed, Oct 24, 2018 at 09:49:46PM +0300, Gabriel Ivăncescu wrote:
> Windows doesn't reset and re-enumerate it everytime autocompletion happens,
> and it also sorts the strings. This matches it more closely and makes it
> more useable on large lists as well.
> Signed-off-by: Gabriel Ivăncescu
>
> v2: Merged the first 3 patches, used qsort, replaced goto that broke out
> of nested scope with a BOOL check, and moved the goto failure path at the
> end outside of any blocks.
>
> dlls/shell32/autocomplete.c | 288 +++++++++++++++++++++++++++++++++++---------
>  1 file changed, 228 insertions(+), 60 deletions(-)
>
> diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c
> index dfe7638..751bda0 100644
> --- a/dlls/shell32/autocomplete.c
> +++ b/dlls/shell32/autocomplete.c
> @@ -25,7 +25,6 @@
> -
>
> implement ACO_FILTERPREFIXES style
> -
>
> implement ACO_RTLREADING style
> -
>
> implement ResetEnumerator
> -
> - string compares should be case-insensitive, the content of the list should be sorted
>
> */
>
> #include "config.h"
> @@ -62,6 +61,8 @@ typedef struct
>      LONG ref;
>      BOOL initialized;
>      BOOL enabled;
> - UINT enum_strs_num;
> - WCHAR **enum_strs;
> HWND hwndEdit;
> HWND hwndListBox;
> WNDPROC wpOrigEditProc;
>
> @@ -103,10 +104,160 @@ static void set_text_and_selection(IAutoCompleteImpl *ac, HWND hwnd, WCHAR *text
>          CallWindowProcW(proc, hwnd, EM_SETSEL, start, end);
>  }
>
> +static int enumerate_strings_cmpfn(const void *a, const void *b)
> +{
> - return strcmpiW(*(WCHAR* const*)a, *(WCHAR* const*)b);
>
> +}
> -
>
> +static void enumerate_strings(IAutoCompleteImpl *ac)
> +{
> - /*
> -
>   Enumerate all of the strings and sort them in the internal list. Rough summary:
> -
> -
>     - Enumerate the strings and place their addresses in a chain of blocks (stack-like)
> -
>     - Copy the pointers from the blocks into a contiguous array/list
> -
>     - Sort the contiguous array/list

Why don't you add them to a contiguous array as you go, by realloc'ing the array.
This would avoid all this complicated block stuff (and if the reallocs don't
need to move, you avoid the copy).
> -
> -
>   We don't free the enumerated strings (except on error) to avoid needless
> -
>   copies, until the next reset (or the object itself is destroyed)
> - */
> - struct
> - {
> -
>    void *prev;
> -
>    LPOLESTR str[1020];
> - } *prevblock, *curblock;
> -
> - UINT i, cur, numstrs = 0;
> - LPOLESTR *strs;
> -
> - prevblock = NULL;
> - for (;;)
> - {
> -
>    LONG rem;
> -
>    BOOL break_enum = FALSE;
> -
> -
>    if ((curblock = heap_alloc(sizeof(*curblock))) == NULL)
> -
>    {
> -
>        if (!prevblock)
> -
>            return;
> -
>        curblock = prevblock;
> -
>        cur = ARRAY_SIZE(curblock->str);
> -
>        goto fail_and_free_blocks;
> -
>    }
> -
>    curblock->prev = prevblock;
> -
>    rem = ARRAY_SIZE(curblock->str);
> -
> -
>    while (rem > 0)
> -
>    {
> -
>        ULONG n = 0;
> -
>        cur = ARRAY_SIZE(curblock->str) - rem;
> -
>        IEnumString_Next(ac->enumstr, rem, &curblock->str[cur], &n);
> -
>        if (n == 0)
> -
>        {
> -
>            break_enum = TRUE;
> -
>            break;
> -
>        }
> -
>        rem -= n;
> -
>    }
> -
>    if (break_enum) break;
> -
>    prevblock = curblock;
> -
>    numstrs += ARRAY_SIZE(curblock->str);
> - }
> -
> - /* Allocate even if there were zero strings enumerated, to mark it non-NULL */
> - numstrs += cur;
> - if ((strs = heap_alloc(numstrs * sizeof(*strs))))
> - {
> -
>    if (numstrs == 0)
> -
>    {
> -
>        ac->enum_strs = strs;
> -
>        ac->enum_strs_num = numstrs;
> -
>        heap_free(curblock);
> -
>        return;
> -
>    }
> -
> -
>    /* Copy the pointers from the chain of blocks to the contiguous list */
> -
>    i = numstrs;
> -
>    do
> -
>    {
> -
>        i -= cur;
> -
>        memcpy(&strs[i], curblock->str, cur * sizeof(*strs));
> -
> -
>        prevblock = curblock->prev;
> -
>        heap_free(curblock);
> -
>        curblock = prevblock;
> -
>        cur = ARRAY_SIZE(curblock->str);
> -
>    } while (curblock);
> -
> -
>    /* Now sort the list */
> -
>    qsort(strs, numstrs, sizeof(*strs), enumerate_strings_cmpfn);
> -
> -
>    ac->enum_strs = strs;
> -
>    ac->enum_strs_num = numstrs;
> -
>    return;
> - }
> -
>
> +fail_and_free_blocks:
> - do
> - {
> -
>    LPOLESTR *str = curblock->str;
> -
>    while (cur--)
> -
>        CoTaskMemFree(str[cur]);
> -
>    prevblock = curblock->prev;
> -
>    heap_free(curblock);
> -
>    curblock = prevblock;
> -
>    cur = ARRAY_SIZE(curblock->str);
> - } while (curblock);
>
> +}
> -
>
> +static UINT find_first_matching_enum_str(IAutoCompleteImpl *ac, WCHAR *text, UINT len)
> +{
> - WCHAR **strs = ac->enum_strs;
> - UINT index = ~0, a = 0, b = ac->enum_strs_num;
> - while (a < b)
> - {
> -
>    UINT i = (a + b - 1) / 2;
> -
>    int cmp = strncmpiW(text, strs[i], len);
> -
>    if (cmp == 0) index = i;
> -
>    if (cmp <= 0) b = i;
> -
>    else          a = i + 1;
> - }
> - return index;
>
> +}

Can't you use bsearch() ?
> +static void free_enum_strs(IAutoCompleteImpl *ac)
> +{
> - WCHAR **strs = ac->enum_strs;
> - if (strs)
> - {
> -
>    UINT i = ac->enum_strs_num;
> -
>    ac->enum_strs = NULL;
> -
>    while (i--)
> -
>        CoTaskMemFree(strs[i]);
> -
>    heap_free(strs);
> - }
>
> +}
> -
>
> static void hide_listbox(IAutoCompleteImpl *ac, HWND hwnd)
>  {
>      ShowWindow(hwnd, SW_HIDE);
>      SendMessageW(hwnd, LB_RESETCONTENT, 0, 0);
> - free_enum_strs(ac);
>
> +}
> -
>
> +static void show_listbox(IAutoCompleteImpl *ac, UINT cnt)
> +{
> - RECT r;
> - UINT width, height;
> -
> - GetWindowRect(ac->hwndEdit, &r);
> - SendMessageW(ac->hwndListBox, LB_CARETOFF, 0, 0);
> -
> - /* Windows XP displays 7 lines at most, then it uses a scroll bar */
> - height = SendMessageW(ac->hwndListBox, LB_GETITEMHEIGHT, 0, 0) * min(cnt + 1, 7);
> - width = r.right - r.left;
> -
> - SetWindowPos(ac->hwndListBox, HWND_TOP, r.left, r.bottom + 1, width, height, SWP_SHOWWINDOW);
>
> }

There's quite a lot of code movement going on from here on down.  I'd
suggest pulling out the show_listbox() helper from autocomplete_text()
first, before adding the caching stuff.
> static size_t format_quick_complete(WCHAR *dst, const WCHAR *qc, const WCHAR *str, size_t str_len)
> @@ -225,7 +376,11 @@ static LRESULT change_selection(IAutoCompleteImpl *ac, HWND hwnd, UINT key)
>
> static BOOL do_aclist_expand(IAutoCompleteImpl *ac, WCHAR *txt, WCHAR *last_delim)
>  {
> - WCHAR c = last_delim[1];
> - WCHAR c;
> - free_enum_strs(ac);
> - IEnumString_Reset(ac->enumstr);  /* call before expand */
> -
> - c = last_delim[1];
> last_delim[1] = '\0';
> IACList_Expand(ac->aclist, txt);
> last_delim[1] = c;
>
> @@ -261,6 +416,9 @@ static BOOL aclist_expand(IAutoCompleteImpl *ac, WCHAR *txt)
>          while (i--)
>              if (strchrW(delims, txt[i]))
>                  return do_aclist_expand(ac, txt, &txt[i]);
> -
> -
>    /* Windows doesn't expand without a delim, but it does reset */
> -
>    free_enum_strs(ac);
>
> }
>
> return FALSE;
>
> @@ -293,11 +451,65 @@ static void autoappend_str(IAutoCompleteImpl *ac, WCHAR *text, UINT len, WCHAR *
>          heap_free(tmp);
>  }
>
> +static BOOL display_matching_strs(IAutoCompleteImpl *ac, WCHAR *text, UINT len,
> -
>                              HWND hwnd, enum autoappend_flag flag)
>
> +{

Likewise the filling listbox code should be pulled out before adding the caching stuff.

In other words, in the patch the finally adds the cache, there shouldn't be (m)any
changes to autocomplete_text(), just to its helper functions.

Huw.

[Gabriel Ivăncescu]

On Thu, Oct 25, 2018 at 3:43 PM Huw Davies  wrote:
> Why don't you add them to a contiguous array as you go, by realloc'ing the array.
> This would avoid all this complicated block stuff (and if the reallocs don't
> need to move, you avoid the copy).

Wouldn't that be a problem if there's a lot of strings to enumerate?
There will be a huge amount of reallocations. Obviously, it's only in
*those* cases that performance even matters, not when the amount of
strings is small (thinking in range about 500k or more).

Also note that the copy is only done due to qsort; previously, there
was no copy needed, since Merge Sort was done directly on the blocks
in pairs first, and moved to the list -- in other words, it's probably
temporary for now to avoid more changes later.
> Can't you use bsearch() ?

I don't think that's possible since I need to get the *first* element
that starts with the given string, not just any matching element. Note
that the search keeps on despite the fact an element is found, but it
remembers the last cmp that was zero.

FWIW I looked at the listbox string search now, and it does something
similar... Also I think binary search is way too simple to even need
bsearch IMO, it would probably add more code even if it could have
been used (an extra function for it...).
> There's quite a lot of code movement going on from here on down.  I'd
> suggest pulling out the show_listbox() helper from autocomplete_text()
> first, before adding the caching stuff.

Ok, I'll do that. Originally it was a smaller patch since it was split
so I forgot to refactor. :-)
> Likewise the filling listbox code should be pulled out before adding the caching stuff.
>
> In other words, in the patch the finally adds the cache, there shouldn't be (m)any
> changes to autocomplete_text(), just to its helper functions.
>
> Huw.

Ok will do.

[Huw Davies]

On 25 Oct 2018, at 14:48, Gabriel Ivăncescu  wrote:
> On Thu, Oct 25, 2018 at 3:43 PM Huw Davies  wrote:
> > Why don't you add them to a contiguous array as you go, by realloc'ing the array.
> > This would avoid all this complicated block stuff (and if the reallocs don't
> > need to move, you avoid the copy).
>
> Wouldn't that be a problem if there's a lot of strings to enumerate?
> There will be a huge amount of reallocations. Obviously, it's only in
> *those* cases that performance even matters, not when the amount of
> strings is small (thinking in range about 500k or more).

Not if you grow the alloc size exponentially.

Huw.

[Gabriel Ivăncescu]

On Thu, Oct 25, 2018 at 5:58 PM Huw Davies  wrote:
> Not if you grow the alloc size exponentially.
>
> Huw.

Yeah, that makes sense, but are you sure you want me to do that?
Here's my reasoning as to why:

Since this code is there and isn't *too* difficult as it is (I hope?),
plus it's also better for the (eventual?) merge sort patch, since it's
much more flexible than other sorts, so that would have to either be
split later or make the pending patch a larger patch to change the
realloc to the chain of blocks if we go with it. (it's friendly to the
cache since it sorts pairs from the end first, the last items in the
cache will be the first ones, where the sort will start from)

I *know* that currently it doesn't mean much, but it will be easier on
me for later pending patches already done, that's why I'm
asking/hoping to change your mind just on this one.

As a side note, since the patches don't really show it: I tried many
different methods for the enumeration (because I was getting
unacceptable performance/slugginess for my use-case) but I ended up
with the situation you saw originally due to profiling and I found out
the hard way why bottom-up merge sort is really bad for performance in
the process... :-)

[Huw Davies]

On 25 Oct 2018, at 16:10, Gabriel Ivăncescu  wrote:
> On Thu, Oct 25, 2018 at 5:58 PM Huw Davies  wrote:
> > Not if you grow the alloc size exponentially.
>
> Yeah, that makes sense, but are you sure you want me to do that?
> Here's my reasoning as to why:
>
> Since this code is there and isn't *too* difficult as it is (I hope?),
> plus it's also better for the (eventual?) merge sort patch, since it's
> much more flexible than other sorts, so that would have to either be
> split later or make the pending patch a larger patch to change the
> realloc to the chain of blocks if we go with it. (it's friendly to the
> cache since it sorts pairs from the end first, the last items in the
> cache will be the first ones, where the sort will start from)
>
> I *know* that currently it doesn't mean much, but it will be easier on
> me for later pending patches already done, that's why I'm
> asking/hoping to change your mind just on this one.

Yes, I'm sure.  We can't have code in Wine just in case it's useful
in the future.

Huw.