[PATCH v3 0/5] MR1249: uiautomationcore: Implement UiaFind.

[Connor McAdams (＠cmcadams)]

--
  v3: uiautomationcore: Add support for returning multiple HUIANODEs from UiaFind.
      uiautomationcore: Store traverse_uia_node_tree() results in a dynamic array.
      uiautomationcore: Add support for ExcludeRoot parameter in UiaFind.
      uiautomationcore: Partially implement UiaFind.
      uiautomationcore: Add UiaFind stub.

https://gitlab.winehq.org/wine/wine/-/merge_requests/1249

[PATCH v3 1/5] uiautomationcore: Add UiaFind stub.

[Connor McAdams]

From: Connor McAdams

Signed-off-by: Connor McAdams 
---
 dlls/uiautomationcore/tests/uiautomation.c  | 1042 +++++++++++++++++++
 dlls/uiautomationcore/uia_client.c          |   10 +
 dlls/uiautomationcore/uiautomationcore.spec |    2 +-
 include/uiautomationcoreapi.h               |    9 +
 4 files changed, 1062 insertions(+), 1 deletion(-)

diff --git a/dlls/uiautomationcore/tests/uiautomation.c b/dlls/uiautomationcore/tests/uiautomation.c
index 827c23e26ef..d0498efe9c4 100644
--- a/dlls/uiautomationcore/tests/uiautomation.c
+++ b/dlls/uiautomationcore/tests/uiautomation.c
@@ -2184,6 +2184,10 @@ DEFINE_PROVIDER(hwnd_child);
 DEFINE_PROVIDER(hwnd_child2);
 DEFINE_PROVIDER(nc_child);
 DEFINE_PROVIDER(nc_child2);
+DEFINE_PROVIDER(child_child);
+DEFINE_PROVIDER(child_child2);
+DEFINE_PROVIDER(child2_child);
+DEFINE_PROVIDER(child2_child_child);

static IAccessible *acc_client;
 static IRawElementProviderSimple *prov_root;
@@ -8203,6 +8207,1043 @@ static void test_UiaNavigate(void)
     UnregisterClassA("UiaNavigate class", NULL);
 }

+static void set_find_params(struct UiaFindParams *params, int max_depth, BOOL find_first, BOOL exclude_root,
+        struct UiaCondition *find_cond)
+{
+    params->MaxDepth = max_depth;
+    params->FindFirst = find_first;
+    params->ExcludeRoot = exclude_root;
+    params->pFindCondition = find_cond;
+}
+
+static void set_provider_prop_override(struct Provider *prov, struct Provider_prop_override *override, int count)
+{
+    prov->prop_override = override;
+    prov->prop_override_count = count;
+}
+
+static void set_property_override(struct Provider_prop_override *override, int prop_id, VARIANT *val)
+{
+    override->prop_id = prop_id;
+    override->val = *val;
+}
+
+static void initialize_provider(struct Provider *prov, int prov_opts, HWND hwnd)
+{
+    prov->prov_opts = prov_opts;
+    prov->hwnd = hwnd;
+    prov->ret_invalid_prop_type = FALSE;
+    prov->expected_tid = 0;
+    prov->runtime_id[0] = prov->runtime_id[1] = 0;
+    prov->last_call_tid = 0;
+    prov->ignore_hwnd_prop = FALSE;
+    prov->override_hwnd = NULL;
+    prov->prop_override = NULL;
+    prov->prop_override_count = 0;
+}
+
+static void initialize_provider_tree(void)
+{
+    initialize_provider(&Provider, ProviderOptions_ServerSideProvider, NULL);
+    initialize_provider(&Provider_child, ProviderOptions_ServerSideProvider, NULL);
+    initialize_provider(&Provider_child_child, ProviderOptions_ServerSideProvider, NULL);
+    initialize_provider(&Provider_child_child2, ProviderOptions_ServerSideProvider, NULL);
+    initialize_provider(&Provider_child2, ProviderOptions_ServerSideProvider, NULL);
+    initialize_provider(&Provider_child2_child, ProviderOptions_ServerSideProvider, NULL);
+    initialize_provider(&Provider_child2_child_child, ProviderOptions_ServerSideProvider, NULL);
+}
+
+static void set_provider_root_and_parent(struct Provider *prov, struct Provider *root, struct Provider *parent)
+{
+    if (parent)
+        prov->parent = &parent->IRawElementProviderFragment_iface;
+    else
+        prov->parent = NULL;
+
+    if (root)
+        prov->frag_root = &root->IRawElementProviderFragmentRoot_iface;
+    else
+        prov->frag_root = NULL;
+}
+
+static void set_provider_children(struct Provider *prov, struct Provider *first_child, struct Provider *last_child)
+{
+    if (first_child)
+        prov->first_child = &first_child->IRawElementProviderFragment_iface;
+    else
+        prov->first_child = NULL;
+
+    if (last_child)
+        prov->last_child = &last_child->IRawElementProviderFragment_iface;
+    else
+        prov->last_child = NULL;
+}
+
+static void set_provider_siblings(struct Provider *prov, struct Provider *prev_sibling, struct Provider *next_sibling)
+{
+    if (prev_sibling)
+        prov->prev_sibling = &prev_sibling->IRawElementProviderFragment_iface;
+    else
+        prov->prev_sibling = NULL;
+
+    if (next_sibling)
+        prov->next_sibling = &next_sibling->IRawElementProviderFragment_iface;
+    else
+        prov->next_sibling = NULL;
+}
+
+#define test_find_sa_results( tree_structs, offsets, exp_elems, exp_tree_struct, exp_offsets ) \
+        test_find_sa_results_( (tree_structs), (offsets), (exp_elems), (exp_tree_struct), (exp_offsets), __FILE__, __LINE__)
+static void test_find_sa_results_(SAFEARRAY *tree_structs, SAFEARRAY *offsets, LONG exp_elems,
+        const WCHAR **exp_tree_struct, int *exp_offset, const char *file, int line)
+{
+    LONG lbound, ubound, elems;
+    HRESULT hr;
+    VARTYPE vt;
+    UINT dims;
+    LONG i;
+
+    /* Tree structures SA. */
+    hr = SafeArrayGetVartype(tree_structs, &vt);
+    ok_(file, line)(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok_(file, line)(vt == VT_BSTR, "Unexpected tree structures sa vt %d\n", vt);
+    dims = SafeArrayGetDim(tree_structs);
+    ok_(file, line)(dims == 1, "Unexpected tree structures sa dims %d\n", dims);
+
+    lbound = ubound = elems = 0;
+    hr = SafeArrayGetLBound(tree_structs, 1, &lbound);
+    ok_(file, line)(hr == S_OK, "Unexpected hr %#lx for SafeArrayGetLBound\n", hr);
+    ok_(file, line)(!lbound, "Unexpected lbound %ld\n", lbound);
+
+    hr = SafeArrayGetUBound(tree_structs, 1, &ubound);
+    ok_(file, line)(hr == S_OK, "Unexpected hr %#lx for SafeArrayGetUBound\n", hr);
+
+    elems = (ubound - lbound) + 1;
+    ok_(file, line)(exp_elems == elems, "Unexpected elems %ld\n", elems);
+
+    /* Offsets SA. */
+    hr = SafeArrayGetVartype(offsets, &vt);
+    ok_(file, line)(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok_(file, line)(vt == VT_I4, "Unexpected offsets sa vt %d\n", vt);
+    dims = SafeArrayGetDim(offsets);
+    ok_(file, line)(dims == 1, "Unexpected offsets sa dims %d\n", dims);
+
+    lbound = ubound = elems = 0;
+    hr = SafeArrayGetLBound(offsets, 1, &lbound);
+    ok_(file, line)(hr == S_OK, "Unexpected hr %#lx for SafeArrayGetLBound\n", hr);
+    ok_(file, line)(!lbound, "Unexpected lbound %ld\n", lbound);
+
+    hr = SafeArrayGetUBound(offsets, 1, &ubound);
+    ok_(file, line)(hr == S_OK, "Unexpected hr %#lx for SafeArrayGetUBound\n", hr);
+
+    elems = (ubound - lbound) + 1;
+    ok_(file, line)(exp_elems == elems, "Unexpected elems %ld\n", elems);
+
+    for (i = 0; i < exp_elems; i++)
+    {
+        BSTR tree_struct;
+        int offset;
+
+        hr = SafeArrayGetElement(tree_structs, &i, &tree_struct);
+        ok_(file, line)(hr == S_OK, "Unexpected hr %#lx\n", hr);
+        ok_(file, line)(!wcscmp(tree_struct, exp_tree_struct[i]), "Unexpected tree structure %s\n", debugstr_w(tree_struct));
+        SysFreeString(tree_struct);
+
+        hr = SafeArrayGetElement(offsets, &i, &offset);
+        ok_(file, line)(hr == S_OK, "Unexpected hr %#lx\n", hr);
+        ok_(file, line)(exp_offset[i] == offset, "Unexpected offset %d\n", offset);
+    }
+}
+
+static const struct prov_method_sequence find_seq1[] = {
+    { &Provider, FRAG_GET_RUNTIME_ID },
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child_child),
+    { &Provider_child_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    { &Provider_child_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child_child2),
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child2),
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child2_child),
+    { &Provider_child2_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child2_child_child),
+    { &Provider_child2_child_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    { &Provider_child2_child_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2_child_child, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider_child2_child),
+    { &Provider_child2_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2_child, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider_child2),
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider),
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    /* Only done on Win10v1507 and below. */
+    { &Provider, FRAG_NAVIGATE, METHOD_OPTIONAL }, /* NavigateDirection_Parent */
+    { &Provider, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child2_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child2_child_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { 0 },
+};
+
+static const struct prov_method_sequence find_seq2[] = {
+    { &Provider, FRAG_GET_RUNTIME_ID },
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child2),
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider),
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    /* Only done on Win10v1507 and below. */
+    { &Provider, FRAG_NAVIGATE, METHOD_OPTIONAL }, /* NavigateDirection_Parent */
+    { &Provider, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { 0 },
+};
+
+static const struct prov_method_sequence find_seq3[] = {
+    { &Provider, FRAG_GET_RUNTIME_ID },
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child2),
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider),
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    /* Only done on Win10v1507 and below. */
+    { &Provider, FRAG_NAVIGATE, METHOD_OPTIONAL }, /* NavigateDirection_Parent */
+    { &Provider_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { 0 },
+};
+
+static const struct prov_method_sequence find_seq4[] = {
+    { &Provider, FRAG_GET_RUNTIME_ID },
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { 0 },
+};
+
+static const struct prov_method_sequence find_seq5[] = {
+    { &Provider_child, FRAG_GET_RUNTIME_ID },
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child2),
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider),
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider),
+    { &Provider_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { 0 },
+};
+
+static const struct prov_method_sequence find_seq6[] = {
+    { &Provider_child, FRAG_GET_RUNTIME_ID },
+    { &Provider_child, FRAG_GET_RUNTIME_ID },
+    { &Provider_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { 0 },
+};
+
+static const struct prov_method_sequence find_seq7[] = {
+    { &Provider, FRAG_GET_RUNTIME_ID },
+    { &Provider, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child_child),
+    { &Provider_child_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider_child_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child_child2),
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child2),
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider),
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    /* Only done on Win10v1507 and below. */
+    { &Provider, FRAG_NAVIGATE, METHOD_OPTIONAL }, /* NavigateDirection_Parent */
+    { &Provider, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { 0 },
+};
+
+static const struct prov_method_sequence find_seq8[] = {
+    { &Provider, FRAG_GET_RUNTIME_ID },
+    { &Provider, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child_child),
+    { &Provider_child_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider_child_child, FRAG_GET_RUNTIME_ID },
+    { &Provider_child_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child_child2),
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider_child_child2, FRAG_GET_RUNTIME_ID },
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, FRAG_GET_RUNTIME_ID },
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child2),
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider_child2, FRAG_GET_RUNTIME_ID },
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider),
+    { &Provider, FRAG_GET_RUNTIME_ID },
+    { &Provider, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { 0 },
+};
+
+static const struct prov_method_sequence find_seq9[] = {
+    { &Provider_child_child2, FRAG_GET_RUNTIME_ID },
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child2),
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child2_child),
+    { &Provider_child2_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child2_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider_child2_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2_child, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider_child2),
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider),
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider),
+    { &Provider, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    /* Only done on Win10v1507 and below. */
+    { &Provider, FRAG_NAVIGATE, METHOD_OPTIONAL }, /* NavigateDirection_Parent */
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { &Provider_child2_child, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { 0 },
+};
+
+static const struct prov_method_sequence find_seq10[] = {
+    { &Provider, FRAG_GET_RUNTIME_ID },
+    { &Provider, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child_child),
+    { &Provider_child_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    { &Provider_child_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child_child2),
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child2),
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child2_child),
+    { &Provider_child2_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child2_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child2_child_child),
+    { &Provider_child2_child_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child2_child_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    { &Provider_child2_child_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2_child_child, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider_child2_child),
+    { &Provider_child2_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2_child, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider_child2),
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider_child2, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    NODE_CREATE_SEQ(&Provider),
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_Parent */
+    /* Only done on Win10v1507 and below. */
+    { &Provider, FRAG_NAVIGATE, METHOD_OPTIONAL }, /* NavigateDirection_Parent */
+    { &Provider_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { 0 },
+};
+
+static const struct prov_method_sequence find_seq11[] = {
+    { &Provider, FRAG_GET_RUNTIME_ID },
+    { &Provider, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child),
+    { &Provider_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    NODE_CREATE_SEQ(&Provider_child_child),
+    { &Provider_child_child, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child_child, FRAG_NAVIGATE }, /* NavigateDirection_FirstChild */
+    { &Provider_child_child, FRAG_NAVIGATE }, /* NavigateDirection_NextSibling */
+    NODE_CREATE_SEQ(&Provider_child_child2),
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsContentElementPropertyId */
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE }, /* UIA_IsControlElementPropertyId */
+    { &Provider_child_child2, PROV_GET_PROPERTY_VALUE, METHOD_TODO }, /* UIA_ProviderDescriptionPropertyId */
+    { 0 },
+};
+
+static void test_UiaFind(void)
+{
+    struct Provider_prop_override prop_override;
+    LONG exp_lbound[2], exp_elems[2], idx[2], i;
+    SAFEARRAY *out_req, *offsets, *tree_structs;
+    struct node_provider_desc exp_node_desc[7];
+    struct UiaPropertyCondition prop_cond[2];
+    struct UiaCacheRequest cache_req;
+    struct UiaFindParams find_params;
+    const WCHAR *exp_tree_struct[7];
+    HUIANODE node, node2;
+    int exp_offset[6];
+    HRESULT hr;
+    VARIANT v;
+
+    CoInitializeEx(NULL, COINIT_MULTITHREADED);
+
+    set_provider_root_and_parent(&Provider, &Provider, NULL);
+    set_provider_children(&Provider, &Provider_child, &Provider_child2);
+    set_provider_siblings(&Provider, NULL, NULL);
+
+    set_provider_root_and_parent(&Provider_child, &Provider, &Provider);
+    set_provider_children(&Provider_child, &Provider_child_child, &Provider_child_child2);
+    set_provider_siblings(&Provider_child, NULL, &Provider_child2);
+
+    set_provider_root_and_parent(&Provider_child_child, &Provider, &Provider_child);
+    set_provider_children(&Provider_child_child, NULL, NULL);
+    set_provider_siblings(&Provider_child_child, NULL, &Provider_child_child2);
+
+    set_provider_root_and_parent(&Provider_child_child2, &Provider, &Provider_child);
+    set_provider_children(&Provider_child_child2, NULL, NULL);
+    set_provider_siblings(&Provider_child_child2, &Provider_child_child, NULL);
+
+    set_provider_root_and_parent(&Provider_child2, &Provider, &Provider);
+    set_provider_children(&Provider_child2, &Provider_child2_child, &Provider_child2_child);
+    set_provider_siblings(&Provider_child2, &Provider_child, NULL);
+
+    set_provider_root_and_parent(&Provider_child2_child, &Provider, &Provider_child2);
+    set_provider_children(&Provider_child2_child, &Provider_child2_child_child, &Provider_child2_child_child);
+    set_provider_siblings(&Provider_child2_child, NULL, NULL);
+
+    set_provider_root_and_parent(&Provider_child2_child_child, &Provider, &Provider_child2_child);
+    set_provider_children(&Provider_child2_child_child, NULL, NULL);
+    set_provider_siblings(&Provider_child2_child_child, NULL, NULL);
+
+    initialize_provider_tree();
+
+    for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
+        init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);
+
+    hr = UiaNodeFromProvider(&Provider.IRawElementProviderSimple_iface, &node);
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(Provider.ref == 2, "Unexpected refcnt %ld\n", Provider.ref);
+
+    hr = UiaGetPropertyValue(node, UIA_ProviderDescriptionPropertyId, &v);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx\n", hr);
+    if (SUCCEEDED(hr))
+    {
+        check_node_provider_desc_prefix(V_BSTR(&v), GetCurrentProcessId(), NULL);
+        check_node_provider_desc(V_BSTR(&v), L"Main", L"Provider", TRUE);
+        VariantClear(&v);
+    }
+
+    ok_method_sequence(node_from_prov2, NULL);
+
+    /*
+     * Maximum find depth of -1, find first is FALSE, exclude root is FALSE. A
+     * maximum depth of -1 will search the entire tree.
+     */
+    out_req = offsets = tree_structs = NULL;
+    set_cache_request(&cache_req, (struct UiaCondition *)&UiaTrueCondition, TreeScope_Element, NULL, 0, NULL, 0,
+            AutomationElementMode_Full);
+    set_find_params(&find_params, -1, FALSE, FALSE, (struct UiaCondition *)&UiaTrueCondition);
+    hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    todo_wine ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);
+    todo_wine ok(Provider_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child.ref);
+    todo_wine ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
+    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+    todo_wine ok(Provider_child2_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child2_child.ref);
+    todo_wine ok(Provider_child2_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child2_child_child.ref);
+
+    if (SUCCEEDED(hr))
+    {
+        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
+        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child", TRUE);
+        add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child_child", TRUE);
+        add_provider_desc(&exp_node_desc[3], L"Main", L"Provider_child_child2", TRUE);
+        add_provider_desc(&exp_node_desc[4], L"Main", L"Provider_child2", TRUE);
+        add_provider_desc(&exp_node_desc[5], L"Main", L"Provider_child2_child", TRUE);
+        add_provider_desc(&exp_node_desc[6], L"Main", L"Provider_child2_child_child", TRUE);
+        exp_lbound[0] = exp_lbound[1] = 0;
+        exp_elems[0] = 7;
+        exp_elems[1] = 1;
+
+        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+
+        for (i = 0; i < exp_elems[0]; i++)
+        {
+            exp_offset[i] = i;
+            exp_tree_struct[i] = L"P)";
+        }
+        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+        ok_method_sequence(find_seq1, "find_seq1");
+    }
+
+    SafeArrayDestroy(out_req);
+    SafeArrayDestroy(offsets);
+    SafeArrayDestroy(tree_structs);
+
+    for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
+        init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);
+
+    /*
+     * Maximum find depth of 1, find first is FALSE, exclude root is FALSE.
+     */
+    set_cache_request(&cache_req, (struct UiaCondition *)&UiaTrueCondition, TreeScope_Element, NULL, 0, NULL, 0,
+            AutomationElementMode_Full);
+    set_find_params(&find_params, 1, FALSE, FALSE, (struct UiaCondition *)&UiaTrueCondition);
+    hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    todo_wine ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);
+    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+
+    if (SUCCEEDED(hr))
+    {
+        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
+        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child", TRUE);
+        add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child2", TRUE);
+        exp_lbound[0] = exp_lbound[1] = 0;
+        exp_elems[0] = 3;
+        exp_elems[1] = 1;
+
+        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+
+        for (i = 0; i < exp_elems[0]; i++)
+        {
+            exp_offset[i] = i;
+            exp_tree_struct[i] = L"P)";
+        }
+
+        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+        ok_method_sequence(find_seq2, "find_seq2");
+    }
+
+    SafeArrayDestroy(out_req);
+    SafeArrayDestroy(offsets);
+    SafeArrayDestroy(tree_structs);
+
+    for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
+        init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);
+
+    /*
+     * Maximum find depth of 1, find first is FALSE, exclude root is TRUE.
+     */
+    set_cache_request(&cache_req, (struct UiaCondition *)&UiaTrueCondition, TreeScope_Element, NULL, 0, NULL, 0,
+            AutomationElementMode_Full);
+    set_find_params(&find_params, 1, FALSE, TRUE, (struct UiaCondition *)&UiaTrueCondition);
+    hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    todo_wine ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);
+    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+
+    if (SUCCEEDED(hr))
+    {
+        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
+        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child2", TRUE);
+        exp_lbound[0] = exp_lbound[1] = 0;
+        exp_elems[0] = 2;
+        exp_elems[1] = 1;
+
+        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+
+        for (i = 0; i < exp_elems[0]; i++)
+        {
+            exp_offset[i] = i;
+            exp_tree_struct[i] = L"P)";
+        }
+        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+        ok_method_sequence(find_seq3, "find_seq3");
+    }
+
+    SafeArrayDestroy(out_req);
+    SafeArrayDestroy(offsets);
+    SafeArrayDestroy(tree_structs);
+
+    for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
+        init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);
+
+    /*
+     * Maximum find depth of 1, find first is TRUE, exclude root is TRUE. Will
+     * retrieve only Provider_child.
+     */
+    set_cache_request(&cache_req, (struct UiaCondition *)&UiaTrueCondition, TreeScope_Element, NULL, 0, NULL, 0,
+            AutomationElementMode_Full);
+    set_find_params(&find_params, 1, TRUE, TRUE, (struct UiaCondition *)&UiaTrueCondition);
+    hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    todo_wine ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);
+
+    node2 = NULL;
+    if (SUCCEEDED(hr))
+    {
+        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
+        exp_lbound[0] = exp_lbound[1] = 0;
+        exp_elems[0] = exp_elems[1] = 1;
+
+        idx[0] = idx[1] = 0;
+        hr = SafeArrayGetElement(out_req, idx, &v);
+        ok(hr == S_OK, "Unexpected hr %#lx\n", hr);
+
+        /* node2 is now set as Provider_child. */
+        hr = UiaHUiaNodeFromVariant(&v, &node2);
+        ok(hr == S_OK, "Unexpected hr %#lx\n", hr);
+        IUnknown_AddRef((IUnknown *)node2);
+
+        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+
+        for (i = 0; i < exp_elems[0]; i++)
+        {
+            exp_offset[i] = i;
+            exp_tree_struct[i] = L"P)";
+        }
+        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+        ok_method_sequence(find_seq4, "find_seq4");
+    }
+
+    SafeArrayDestroy(out_req);
+    SafeArrayDestroy(offsets);
+    SafeArrayDestroy(tree_structs);
+
+    for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
+        init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);
+
+    /*
+     * Maximum find depth of 0, find first is FALSE, exclude root is FALSE.
+     * Provider_child doesn't have a runtime id for UI Automation to use as a
+     * way to check if it has navigated back to the node that began the
+     * search, so it will get siblings.
+     */
+    set_cache_request(&cache_req, (struct UiaCondition *)&UiaTrueCondition, TreeScope_Element, NULL, 0, NULL, 0,
+            AutomationElementMode_Full);
+    set_find_params(&find_params, 0, FALSE, FALSE, (struct UiaCondition *)&UiaTrueCondition);
+    hr = UiaFind(node2, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+
+    if (SUCCEEDED(hr))
+    {
+        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
+        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child2", TRUE);
+        exp_lbound[0] = exp_lbound[1] = 0;
+        exp_elems[0] = 2;
+        exp_elems[1] = 1;
+
+        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+
+        for (i = 0; i < exp_elems[0]; i++)
+        {
+            exp_offset[i] = i;
+            exp_tree_struct[i] = L"P)";
+        }
+        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+        ok_method_sequence(find_seq5, "find_seq5");
+    }
+
+    SafeArrayDestroy(out_req);
+    SafeArrayDestroy(offsets);
+    SafeArrayDestroy(tree_structs);
+
+    for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
+        init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);
+
+    /*
+     * Maximum find depth of 0, find first is FALSE, exclude root is FALSE.
+     * Provider_child has a runtime id for UI Automation to use as a
+     * way to check if it has navigated back to the node that began the
+     * search, so it will stop at Provider_child.
+     */
+    Provider_child.runtime_id[0] = Provider_child.runtime_id[1] = 0xdeadbeef;
+    set_cache_request(&cache_req, (struct UiaCondition *)&UiaTrueCondition, TreeScope_Element, NULL, 0, NULL, 0,
+            AutomationElementMode_Full);
+    set_find_params(&find_params, 0, FALSE, FALSE, (struct UiaCondition *)&UiaTrueCondition);
+    hr = UiaFind(node2, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+
+    if (SUCCEEDED(hr))
+    {
+        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
+        exp_lbound[0] = exp_lbound[1] = 0;
+        exp_elems[0] = exp_elems[1] = 1;
+
+        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+
+        for (i = 0; i < exp_elems[0]; i++)
+        {
+            exp_offset[i] = i;
+            exp_tree_struct[i] = L"P)";
+        }
+        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+        ok_method_sequence(find_seq6, "find_seq6");
+    }
+
+    SafeArrayDestroy(out_req);
+    SafeArrayDestroy(offsets);
+    SafeArrayDestroy(tree_structs);
+
+    todo_wine ok(UiaNodeRelease(node2), "UiaNodeRelease returned FALSE\n");
+    ok(Provider_child.ref == 1, "Unexpected refcnt %ld\n", Provider_child.ref);
+
+    initialize_provider_tree();
+    for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
+        init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);
+
+    /*
+     * Maximum find depth of 1, find first is FALSE, exclude root is FALSE.
+     * The cache request view condition is used to determine tree depth, if an
+     * element matches the cache request view condition, depth is incremented.
+     * Since Provider_child does not, Provider_child_child, Provider_child_child2,
+     * and Provider_child2 are all considered to be at depth 1.
+     */
+    V_VT(&v) = VT_BOOL;
+    V_BOOL(&v) = VARIANT_FALSE;
+    set_property_condition(&prop_cond[0], UIA_IsContentElementPropertyId, &v, 0);
+    set_property_override(&prop_override, UIA_IsContentElementPropertyId, &v);
+
+    V_VT(&v) = VT_BOOL;
+    V_BOOL(&v) = VARIANT_TRUE;
+    set_property_condition(&prop_cond[1], UIA_IsControlElementPropertyId, &v, 0);
+
+    set_provider_prop_override(&Provider, &prop_override, 1);
+    set_provider_prop_override(&Provider_child2, &prop_override, 1);
+    set_provider_prop_override(&Provider_child_child, &prop_override, 1);
+    set_provider_prop_override(&Provider_child_child2, &prop_override, 1);
+
+    set_cache_request(&cache_req, (struct UiaCondition *)&prop_cond[0], TreeScope_Element, NULL, 0, NULL, 0,
+            AutomationElementMode_Full);
+    set_find_params(&find_params, 1, FALSE, FALSE, (struct UiaCondition *)&prop_cond[1]);
+    hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    todo_wine ok(Provider_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child.ref);
+    todo_wine ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
+    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+
+    if (SUCCEEDED(hr))
+    {
+        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
+        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child_child", TRUE);
+        add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child_child2", TRUE);
+        add_provider_desc(&exp_node_desc[3], L"Main", L"Provider_child2", TRUE);
+        exp_lbound[0] = exp_lbound[1] = 0;
+        exp_elems[0] = 4;
+        exp_elems[1] = 1;
+
+        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+
+        for (i = 0; i < exp_elems[0]; i++)
+        {
+            exp_offset[i] = i;
+            exp_tree_struct[i] = L"P)";
+        }
+        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+        ok_method_sequence(find_seq7, "find_seq7");
+    }
+
+    SafeArrayDestroy(out_req);
+    SafeArrayDestroy(offsets);
+    SafeArrayDestroy(tree_structs);
+
+    initialize_provider_tree();
+    for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
+        init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);
+
+    /*
+     * Same test as before, except Provider has a runtime id.
+     */
+    Provider.runtime_id[0] = Provider.runtime_id[1] = 0xdeadbeef;
+    V_VT(&v) = VT_BOOL;
+    V_BOOL(&v) = VARIANT_FALSE;
+    set_property_condition(&prop_cond[0], UIA_IsContentElementPropertyId, &v, 0);
+    set_property_override(&prop_override, UIA_IsContentElementPropertyId, &v);
+
+    V_VT(&v) = VT_BOOL;
+    V_BOOL(&v) = VARIANT_TRUE;
+    set_property_condition(&prop_cond[1], UIA_IsControlElementPropertyId, &v, 0);
+
+    set_provider_prop_override(&Provider, &prop_override, 1);
+    set_provider_prop_override(&Provider_child2, &prop_override, 1);
+    set_provider_prop_override(&Provider_child_child, &prop_override, 1);
+    set_provider_prop_override(&Provider_child_child2, &prop_override, 1);
+
+    set_cache_request(&cache_req, (struct UiaCondition *)&prop_cond[0], TreeScope_Element, NULL, 0, NULL, 0,
+            AutomationElementMode_Full);
+    set_find_params(&find_params, 1, FALSE, FALSE, (struct UiaCondition *)&prop_cond[1]);
+    hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    todo_wine ok(Provider_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child.ref);
+    todo_wine ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
+    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+
+    if (SUCCEEDED(hr))
+    {
+        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
+        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child_child", TRUE);
+        add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child_child2", TRUE);
+        add_provider_desc(&exp_node_desc[3], L"Main", L"Provider_child2", TRUE);
+        exp_lbound[0] = exp_lbound[1] = 0;
+        exp_elems[0] = 4;
+        exp_elems[1] = 1;
+
+        idx[0] = 2;
+        idx[1] = 0;
+        hr = SafeArrayGetElement(out_req, idx, &v);
+        ok(hr == S_OK, "Unexpected hr %#lx\n", hr);
+
+        /* node2 is now set as Provider_child_child2. */
+        hr = UiaHUiaNodeFromVariant(&v, &node2);
+        ok(hr == S_OK, "Unexpected hr %#lx\n", hr);
+        IUnknown_AddRef((IUnknown *)node2);
+
+        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+
+        for (i = 0; i < exp_elems[0]; i++)
+        {
+            exp_offset[i] = i;
+            exp_tree_struct[i] = L"P)";
+        }
+        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+        ok_method_sequence(find_seq8, "find_seq8");
+    }
+
+    SafeArrayDestroy(out_req);
+    SafeArrayDestroy(offsets);
+    SafeArrayDestroy(tree_structs);
+
+    initialize_provider_tree();
+    for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
+        init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);
+
+    /*
+     * Maximum find depth of 1, find first is FALSE, exclude root is FALSE.
+     * Starting at Provider_child_child2, find will be able to traverse the
+     * tree in the same order as it would if we had started at the tree root
+     * Provider, retrieving Provider_child2 as a sibling and
+     * Provider_child2_child as a node at depth 1.
+     */
+    V_VT(&v) = VT_BOOL;
+    V_BOOL(&v) = VARIANT_FALSE;
+    set_property_condition(&prop_cond[0], UIA_IsContentElementPropertyId, &v, 0);
+
+    V_VT(&v) = VT_BOOL;
+    V_BOOL(&v) = VARIANT_TRUE;
+    set_property_condition(&prop_cond[1], UIA_IsControlElementPropertyId, &v, 0);
+
+    prop_override.prop_id = UIA_IsContentElementPropertyId;
+    V_VT(&prop_override.val) = VT_BOOL;
+    V_BOOL(&prop_override.val) = VARIANT_FALSE;
+    set_provider_prop_override(&Provider_child_child2, &prop_override, 1);
+    set_provider_prop_override(&Provider_child2, &prop_override, 1);
+    set_provider_prop_override(&Provider_child2_child, &prop_override, 1);
+
+    set_cache_request(&cache_req, (struct UiaCondition *)&prop_cond[0], TreeScope_Element, NULL, 0, NULL, 0,
+            AutomationElementMode_Full);
+    set_find_params(&find_params, 1, FALSE, FALSE, (struct UiaCondition *)&prop_cond[1]);
+    hr = UiaFind(node2, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+    todo_wine ok(Provider_child2_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child2_child.ref);
+
+    if (SUCCEEDED(hr))
+    {
+        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child_child2", TRUE);
+        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child2", TRUE);
+        add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child2_child", TRUE);
+        exp_lbound[0] = exp_lbound[1] = 0;
+        exp_elems[0] = 3;
+        exp_elems[1] = 1;
+
+        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+
+        for (i = 0; i < exp_elems[0]; i++)
+        {
+            exp_offset[i] = i;
+            exp_tree_struct[i] = L"P)";
+        }
+        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+        ok_method_sequence(find_seq9, "find_seq9");
+    }
+
+    SafeArrayDestroy(out_req);
+    SafeArrayDestroy(offsets);
+    SafeArrayDestroy(tree_structs);
+
+    initialize_provider_tree();
+    for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
+        init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);
+
+    todo_wine ok(UiaNodeRelease(node2), "UiaNodeRelease returned FALSE\n");
+    ok(Provider_child_child2.ref == 1, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
+
+    /*
+     * Maximum find depth of 1, find first is FALSE, exclude root is TRUE.
+     * Exclude root applies to the first node that matches the view
+     * condition, and not the node that is passed into UiaFind(). Since
+     * Provider doesn't match our view condition here, Provider_child will be
+     * excluded.
+     */
+    V_VT(&v) = VT_BOOL;
+    V_BOOL(&v) = VARIANT_FALSE;
+    set_property_condition(&prop_cond[0], UIA_IsContentElementPropertyId, &v, 0);
+    set_property_override(&prop_override, UIA_IsContentElementPropertyId, &v);
+
+    V_VT(&v) = VT_BOOL;
+    V_BOOL(&v) = VARIANT_TRUE;
+    set_property_condition(&prop_cond[1], UIA_IsControlElementPropertyId, &v, 0);
+
+    set_provider_prop_override(&Provider_child, &prop_override, 1);
+    set_provider_prop_override(&Provider_child2, &prop_override, 1);
+
+    set_cache_request(&cache_req, (struct UiaCondition *)&prop_cond[0], TreeScope_Element, NULL, 0, NULL, 0,
+            AutomationElementMode_Full);
+    set_find_params(&find_params, 1, FALSE, TRUE, (struct UiaCondition *)&prop_cond[1]);
+    hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+
+    if (SUCCEEDED(hr))
+    {
+        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child2", TRUE);
+        exp_lbound[0] = exp_lbound[1] = 0;
+        exp_elems[0] = 1;
+        exp_elems[1] = 1;
+
+        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+
+        for (i = 0; i < exp_elems[0]; i++)
+        {
+            exp_offset[i] = i;
+            exp_tree_struct[i] = L"P)";
+        }
+        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+
+        ok_method_sequence(find_seq10, "find_seq10");
+    }
+
+    SafeArrayDestroy(out_req);
+    SafeArrayDestroy(offsets);
+    SafeArrayDestroy(tree_structs);
+
+    initialize_provider_tree();
+    for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
+        init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);
+
+    /*
+     * Maximum find depth of -1, find first is TRUE, exclude root is FALSE.
+     * Provider_child_child2 is the only element in the tree to match our
+     * condition.
+     */
+    V_VT(&v) = VT_BOOL;
+    V_BOOL(&v) = VARIANT_FALSE;
+    set_property_condition(&prop_cond[0], UIA_IsContentElementPropertyId, &v, 0);
+    set_property_override(&prop_override, UIA_IsContentElementPropertyId, &v);
+
+    V_VT(&v) = VT_BOOL;
+    V_BOOL(&v) = VARIANT_TRUE;
+    set_property_condition(&prop_cond[1], UIA_IsControlElementPropertyId, &v, 0);
+
+    set_provider_prop_override(&Provider_child_child2, &prop_override, 1);
+
+    set_cache_request(&cache_req, (struct UiaCondition *)&prop_cond[0], TreeScope_Element, NULL, 0, NULL, 0,
+            AutomationElementMode_Full);
+    set_find_params(&find_params, -1, TRUE, FALSE, (struct UiaCondition *)&prop_cond[1]);
+    hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
+    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    todo_wine ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
+
+    if (SUCCEEDED(hr))
+    {
+        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child_child2", TRUE);
+        exp_lbound[0] = exp_lbound[1] = 0;
+        exp_elems[0] = 1;
+        exp_elems[1] = 1;
+
+        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+
+        for (i = 0; i < exp_elems[0]; i++)
+        {
+            exp_offset[i] = i;
+            exp_tree_struct[i] = L"P)";
+        }
+        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+        ok_method_sequence(find_seq11, "find_seq11");
+    }
+
+    SafeArrayDestroy(out_req);
+    SafeArrayDestroy(offsets);
+    SafeArrayDestroy(tree_structs);
+
+    initialize_provider_tree();
+
+    ok(UiaNodeRelease(node), "UiaNodeRelease returned FALSE\n");
+    ok(Provider.ref == 1, "Unexpected refcnt %ld\n", Provider.ref);
+
+    CoUninitialize();
+}
+
 /*
  * Once a process returns a UI Automation provider with
  * UiaReturnRawElementProvider it ends up in an implicit MTA until exit. This
@@ -8268,6 +9309,7 @@ START_TEST(uiautomation)
     launch_test_process(argv[0], "UiaRegisterProviderCallback");
     test_UiaGetUpdatedCache();
     test_UiaNavigate();
+    test_UiaFind();
     if (uia_dll)
     {
         pUiaProviderFromIAccessible = (void *)GetProcAddress(uia_dll, "UiaProviderFromIAccessible");
diff --git a/dlls/uiautomationcore/uia_client.c b/dlls/uiautomationcore/uia_client.c
index dfacebc456f..1025b40446c 100644
--- a/dlls/uiautomationcore/uia_client.c
+++ b/dlls/uiautomationcore/uia_client.c
@@ -2559,3 +2559,13 @@ HRESULT WINAPI UiaNavigate(HUIANODE huianode, enum NavigateDirection dir, struct

return hr;
 }
+
+/***********************************************************************
+ *          UiaFind (uiautomationcore.@)
+ */
+HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, struct UiaCacheRequest *cache_req,
+        SAFEARRAY **out_req, SAFEARRAY **out_offsets, SAFEARRAY **out_tree_structs)
+{
+    FIXME("(%p, %p, %p, %p, %p, %p): stub\n", huianode, find_params, cache_req, out_req, out_offsets, out_tree_structs);
+    return E_NOTIMPL;
+}
diff --git a/dlls/uiautomationcore/uiautomationcore.spec b/dlls/uiautomationcore/uiautomationcore.spec
index c14b457fd47..0ad0cb6f437 100644
--- a/dlls/uiautomationcore/uiautomationcore.spec
+++ b/dlls/uiautomationcore/uiautomationcore.spec
@@ -59,7 +59,7 @@
 @ stdcall UiaDisconnectProvider(ptr)
 @ stub UiaEventAddWindow
 @ stub UiaEventRemoveWindow
-@ stub UiaFind
+@ stdcall UiaFind(ptr ptr ptr ptr ptr ptr)
 @ stub UiaGetErrorDescription
 @ stub UiaGetPatternProvider
 @ stdcall UiaGetPropertyValue(ptr long ptr)
diff --git a/include/uiautomationcoreapi.h b/include/uiautomationcoreapi.h
index 7025392cbbc..efb5eb35d06 100644
--- a/include/uiautomationcoreapi.h
+++ b/include/uiautomationcoreapi.h
@@ -385,6 +385,13 @@ struct UiaWindowClosedEventArgs {
     int cRuntimeIdLen;
 };

+struct UiaFindParams {
+    int MaxDepth;
+    BOOL FindFirst;
+    BOOL ExcludeRoot;
+    struct UiaCondition *pFindCondition;
+};
+
 typedef SAFEARRAY * WINAPI UiaProviderCallback(HWND hwnd,enum ProviderType providerType);

HRESULT WINAPI UiaGetReservedMixedAttributeValue(IUnknown **value);
@@ -409,6 +416,8 @@ HRESULT WINAPI UiaGetUpdatedCache(HUIANODE huianode, struct UiaCacheRequest *cac
         struct UiaCondition *normalize_cond, SAFEARRAY **out_req, BSTR *tree_struct);
 HRESULT WINAPI UiaNavigate(HUIANODE huianode, enum NavigateDirection dir, struct UiaCondition *nav_condition,
         struct UiaCacheRequest *cache_req, SAFEARRAY **out_req, BSTR *tree_struct);
+HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, struct UiaCacheRequest *cache_req, SAFEARRAY **out_req,
+        SAFEARRAY **out_offsets, SAFEARRAY **out_tree_structs);

#ifdef __cplusplus
 }

[PATCH v3 2/5] uiautomationcore: Partially implement UiaFind.

[Connor McAdams]

From: Connor McAdams

Implement UiaFind for single node searches.

Signed-off-by: Connor McAdams 
---
 dlls/uiautomationcore/tests/uiautomation.c |  29 +--
 dlls/uiautomationcore/uia_client.c         | 269 ++++++++++++++++++++-
 2 files changed, 280 insertions(+), 18 deletions(-)

diff --git a/dlls/uiautomationcore/tests/uiautomation.c b/dlls/uiautomationcore/tests/uiautomation.c
index d0498efe9c4..20ff4ddd661 100644
--- a/dlls/uiautomationcore/tests/uiautomation.c
+++ b/dlls/uiautomationcore/tests/uiautomation.c
@@ -9211,26 +9211,23 @@ static void test_UiaFind(void)
             AutomationElementMode_Full);
     set_find_params(&find_params, -1, TRUE, FALSE, (struct UiaCondition *)&prop_cond[1]);
     hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
-    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
-    todo_wine ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);

-    if (SUCCEEDED(hr))
-    {
-        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child_child2", TRUE);
-        exp_lbound[0] = exp_lbound[1] = 0;
-        exp_elems[0] = 1;
-        exp_elems[1] = 1;
+    add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child_child2", TRUE);
+    exp_lbound[0] = exp_lbound[1] = 0;
+    exp_elems[0] = 1;
+    exp_elems[1] = 1;

-        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+    test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);

-        for (i = 0; i < exp_elems[0]; i++)
-        {
-            exp_offset[i] = i;
-            exp_tree_struct[i] = L"P)";
-        }
-        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
-        ok_method_sequence(find_seq11, "find_seq11");
+    for (i = 0; i < exp_elems[0]; i++)
+    {
+        exp_offset[i] = i;
+        exp_tree_struct[i] = L"P)";
     }
+    test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+    ok_method_sequence(find_seq11, "find_seq11");

SafeArrayDestroy(out_req);
     SafeArrayDestroy(offsets);
diff --git a/dlls/uiautomationcore/uia_client.c b/dlls/uiautomationcore/uia_client.c
index 1025b40446c..43331108078 100644
--- a/dlls/uiautomationcore/uia_client.c
+++ b/dlls/uiautomationcore/uia_client.c
@@ -23,6 +23,8 @@

WINE_DEFAULT_DEBUG_CHANNEL(uiautomation);

+static const struct UiaCondition UiaFalseCondition = { ConditionType_False };
+
 static HRESULT get_safearray_bounds(SAFEARRAY *sa, LONG *lbound, LONG *elems)
 {
     LONG ubound;
@@ -873,6 +875,179 @@ static HRESULT navigate_uia_node(struct uia_node *node, int nav_dir, HUIANODE *o
     return S_OK;
 }

+static HRESULT uia_condition_check(HUIANODE node, struct UiaCondition *condition);
+static BOOL uia_condition_matched(HRESULT hr);
+
+/*
+ * Assuming we have a tree that looks like this:
+ *                  +-------+
+ *                  |       |
+ *                  |   1   |
+ *                  |       |
+ *                  +---+---+
+ *                      |
+ *          +-----------+-----------+
+ *          |           |           |
+ *      +---+---+   +---+---+   +---+---+
+ *      |       |   |       |   |       |
+ *      |   2   +---|   3   +---+   4   |
+ *      |       |   |       |   |       |
+ *      +---+---+   +-------+   +-------+
+ *          |
+ *      +---+---+
+ *      |       |
+ *      |   5   |
+ *      |       |
+ *      +-------+
+ * If we start navigation of the tree from node 1, our visit order for a
+ * depth first search would be 1 -> 2 -> 5 -> 3 -> 4.
+ *
+ * However, if we start from the middle of the sequence at node 5 without the
+ * prior context of navigating from nodes 1 and 2, we need to use the function
+ * below to reach node 3, so we can visit the nodes within the tree in the
+ * same order of 5 -> 3 -> 4.
+ */
+static HRESULT traverse_uia_node_tree_siblings(HUIANODE huianode, struct UiaCondition *ascending_stop_cond,
+        int dir, BOOL at_root_level, HUIANODE *out_node)
+{
+    struct uia_node *node = unsafe_impl_from_IWineUiaNode((IWineUiaNode *)huianode);
+    HUIANODE node2 = NULL;
+    HRESULT hr;
+
+    *out_node = NULL;
+
+    IWineUiaNode_AddRef(&node->IWineUiaNode_iface);
+    while (1)
+    {
+        hr = navigate_uia_node(node, dir, &node2);
+        if (FAILED(hr) || node2 || !at_root_level)
+            goto exit;
+
+        hr = navigate_uia_node(node, NavigateDirection_Parent, &node2);
+        if (FAILED(hr) || !node2)
+            goto exit;
+
+        hr = uia_condition_check(node2, ascending_stop_cond);
+        if (FAILED(hr) || uia_condition_matched(hr))
+        {
+            UiaNodeRelease(node2);
+            node2 = NULL;
+            goto exit;
+        }
+
+        IWineUiaNode_Release(&node->IWineUiaNode_iface);
+        node = unsafe_impl_from_IWineUiaNode((IWineUiaNode *)node2);
+    }
+
+exit:
+    IWineUiaNode_Release(&node->IWineUiaNode_iface);
+    *out_node = node2;
+
+    return hr;
+}
+
+/*
+ * This function is used to traverse the 'raw' tree of HUIANODEs using a
+ * depth-first search. As each node in the tree is visited, it is checked
+ * against two conditions.
+ *
+ * The first is the view condition, which is a filter for what is considered to
+ * be a valid node in the current tree 'view'. The view condition essentially
+ * creates a sort of 'virtual' tree. UI Automation provides three default tree
+ * views:
+ * -The 'raw' view has the view condition as ConditionType_True, so the tree
+ *  is completely unfiltered. All nodes are valid.
+ * -The 'control' view contains only nodes that do not return VARIANT_FALSE
+ *  for UIA_IsControlElementPropertyId.
+ * -The 'content' view contains only nodes that do not return VARIANT_FALSE
+ *  for both UIA_IsControlElementPropertyId and UIA_IsContentElementPropertyId.
+ *
+ * If the currently visited node is considered to be valid within our view
+ * condition, it is then checked against the search condition to determine if
+ * it should be returned.
+ */
+static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *view_cond,
+        struct UiaCondition *search_cond, struct UiaCondition *pre_sibling_nav_stop_cond,
+        struct UiaCondition *ascending_stop_cond, int traversal_opts, BOOL at_root_level, int max_depth, int *cur_depth,
+        HUIANODE *out_node)
+{
+    struct uia_node *node = unsafe_impl_from_IWineUiaNode((IWineUiaNode *)huianode);
+    BOOL incr_depth = FALSE;
+    HUIANODE node2;
+    HRESULT hr;
+
+    hr = uia_condition_check(huianode, view_cond);
+    if (FAILED(hr))
+        goto exit;
+
+    if (uia_condition_matched(hr))
+    {
+        /*
+         * If this is a valid node within our treeview, we need to increment
+         * our current depth within the tree.
+         */
+        incr_depth = TRUE;
+        hr = uia_condition_check(huianode, search_cond);
+        if (FAILED(hr))
+            goto exit;
+
+        if (uia_condition_matched(hr))
+        {
+            IWineUiaNode_AddRef((IWineUiaNode *)huianode);
+            *out_node = huianode;
+            hr = S_FALSE;
+            goto exit;
+        }
+    }
+
+    if (incr_depth)
+        (*cur_depth)++;
+
+    /* If we haven't exceeded our maximum traversal depth, visit children of this node. */
+    if (max_depth < 0 || (*cur_depth) <= max_depth)
+    {
+        if (traversal_opts & TreeTraversalOptions_LastToFirstOrder)
+            hr = navigate_uia_node(node, NavigateDirection_LastChild, &node2);
+        else
+            hr = navigate_uia_node(node, NavigateDirection_FirstChild, &node2);
+
+        if (SUCCEEDED(hr) && node2)
+            hr = traverse_uia_node_tree(node2, view_cond, search_cond, pre_sibling_nav_stop_cond, ascending_stop_cond,
+                    traversal_opts, FALSE, max_depth, cur_depth, out_node);
+
+        if (FAILED(hr) || hr == S_FALSE)
+            goto exit;
+    }
+
+    if (incr_depth)
+        (*cur_depth)--;
+
+    /*
+     * Before attempting to visit any siblings of huianode, make sure
+     * huianode doesn't match our stop condition.
+     */
+    hr = uia_condition_check(huianode, pre_sibling_nav_stop_cond);
+    if (FAILED(hr) || uia_condition_matched(hr))
+        goto exit;
+
+    /* Now, check for any siblings to visit. */
+    if (traversal_opts & TreeTraversalOptions_LastToFirstOrder)
+        hr = traverse_uia_node_tree_siblings(huianode, ascending_stop_cond, NavigateDirection_PreviousSibling,
+                at_root_level, &node2);
+    else
+        hr = traverse_uia_node_tree_siblings(huianode, ascending_stop_cond, NavigateDirection_NextSibling,
+                at_root_level, &node2);
+
+    if (SUCCEEDED(hr) && node2)
+        hr = traverse_uia_node_tree(node2, view_cond, search_cond, pre_sibling_nav_stop_cond, ascending_stop_cond,
+                traversal_opts, at_root_level, max_depth, cur_depth, out_node);
+
+exit:
+    UiaNodeRelease(huianode);
+
+    return hr;
+}
+
 /*
  * IWineUiaProvider interface.
  */
@@ -2566,6 +2741,96 @@ HRESULT WINAPI UiaNavigate(HUIANODE huianode, enum NavigateDirection dir, struct
 HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, struct UiaCacheRequest *cache_req,
         SAFEARRAY **out_req, SAFEARRAY **out_offsets, SAFEARRAY **out_tree_structs)
 {
-    FIXME("(%p, %p, %p, %p, %p, %p): stub\n", huianode, find_params, cache_req, out_req, out_offsets, out_tree_structs);
-    return E_NOTIMPL;
+    struct UiaPropertyCondition prop_cond = { ConditionType_Property, UIA_RuntimeIdPropertyId };
+    struct uia_node *node = unsafe_impl_from_IWineUiaNode((IWineUiaNode *)huianode);
+    SAFEARRAY *runtime_id, *req, *offsets, *tree_structs;
+    struct UiaCondition *sibling_stop_cond;
+    int cur_depth = 0;
+    BSTR tree_struct;
+    HUIANODE node2;
+    HRESULT hr;
+    LONG idx;
+
+    TRACE("(%p, %p, %p, %p, %p, %p)\n", huianode, find_params, cache_req, out_req, out_offsets, out_tree_structs);
+
+    if (!node || !find_params || !cache_req || !out_req || !out_offsets || !out_tree_structs)
+        return E_INVALIDARG;
+
+    *out_tree_structs = *out_offsets = *out_req = tree_structs = offsets = req = NULL;
+
+    if (!find_params->FindFirst)
+    {
+        FIXME("Finding more than one HUIANODE is currently unimplemented.\n");
+        return E_NOTIMPL;
+    }
+
+    if (find_params->ExcludeRoot)
+    {
+        FIXME("ExcludeRoot currently unimplemented.\n");
+        return E_NOTIMPL;
+    }
+
+    /*
+     * If the initial node has a runtime ID, we'll use it as a stop
+     * condition.
+     */
+    hr = UiaGetRuntimeId(huianode, &runtime_id);
+    if (SUCCEEDED(hr) && runtime_id)
+    {
+        V_VT(&prop_cond.Value) = VT_I4 | VT_ARRAY;
+        V_ARRAY(&prop_cond.Value) = runtime_id;
+        sibling_stop_cond = (struct UiaCondition *)&prop_cond;
+    }
+    else
+        sibling_stop_cond =  (struct UiaCondition *)&UiaFalseCondition;
+
+    node2 = NULL;
+    IWineUiaNode_AddRef(&node->IWineUiaNode_iface);
+    hr = traverse_uia_node_tree(huianode, cache_req->pViewCondition, find_params->pFindCondition, sibling_stop_cond,
+            cache_req->pViewCondition, TreeTraversalOptions_Default, TRUE, find_params->MaxDepth, &cur_depth, &node2);
+    if (FAILED(hr) || !node2)
+        goto exit;
+
+    if (!(offsets = SafeArrayCreateVector(VT_I4, 0, 1)))
+    {
+        hr = E_FAIL;
+        goto exit;
+    }
+
+    if (!(tree_structs = SafeArrayCreateVector(VT_BSTR, 0, 1)))
+    {
+        hr = E_FAIL;
+        goto exit;
+    }
+
+    hr = UiaGetUpdatedCache(node2, cache_req, NormalizeState_None, NULL, &req, &tree_struct);
+    UiaNodeRelease(node2);
+    if (FAILED(hr))
+        goto exit;
+
+    idx = 0;
+    hr = SafeArrayPutElement(tree_structs, &idx, tree_struct);
+    SysFreeString(tree_struct);
+    if (FAILED(hr))
+        goto exit;
+
+    hr = SafeArrayPutElement(offsets, &idx, &idx);
+    if (FAILED(hr))
+        goto exit;
+
+    *out_tree_structs = tree_structs;
+    *out_offsets = offsets;
+    *out_req = req;
+
+exit:
+    VariantClear(&prop_cond.Value);
+
+    if (FAILED(hr))
+    {
+        SafeArrayDestroy(tree_structs);
+        SafeArrayDestroy(offsets);
+        SafeArrayDestroy(req);
+    }
+
+    return hr;
 }

[PATCH v3 3/5] uiautomationcore: Add support for ExcludeRoot parameter in UiaFind.

[Connor McAdams]

From: Connor McAdams

Signed-off-by: Connor McAdams 
---
 dlls/uiautomationcore/tests/uiautomation.c | 44 ++++++++++------------
 dlls/uiautomationcore/uia_client.c         | 39 +++++++++----------
 2 files changed, 40 insertions(+), 43 deletions(-)

diff --git a/dlls/uiautomationcore/tests/uiautomation.c b/dlls/uiautomationcore/tests/uiautomation.c
index 20ff4ddd661..7275f31f341 100644
--- a/dlls/uiautomationcore/tests/uiautomation.c
+++ b/dlls/uiautomationcore/tests/uiautomation.c
@@ -8835,35 +8835,31 @@ static void test_UiaFind(void)
             AutomationElementMode_Full);
     set_find_params(&find_params, 1, TRUE, TRUE, (struct UiaCondition *)&UiaTrueCondition);
     hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
-    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
-    todo_wine ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);

-    node2 = NULL;
-    if (SUCCEEDED(hr))
-    {
-        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
-        exp_lbound[0] = exp_lbound[1] = 0;
-        exp_elems[0] = exp_elems[1] = 1;
+    add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
+    exp_lbound[0] = exp_lbound[1] = 0;
+    exp_elems[0] = exp_elems[1] = 1;

-        idx[0] = idx[1] = 0;
-        hr = SafeArrayGetElement(out_req, idx, &v);
-        ok(hr == S_OK, "Unexpected hr %#lx\n", hr);
+    idx[0] = idx[1] = 0;
+    hr = SafeArrayGetElement(out_req, idx, &v);
+    ok(hr == S_OK, "Unexpected hr %#lx\n", hr);

-        /* node2 is now set as Provider_child. */
-        hr = UiaHUiaNodeFromVariant(&v, &node2);
-        ok(hr == S_OK, "Unexpected hr %#lx\n", hr);
-        IUnknown_AddRef((IUnknown *)node2);
+    /* node2 is now set as Provider_child. */
+    hr = UiaHUiaNodeFromVariant(&v, &node2);
+    ok(hr == S_OK, "Unexpected hr %#lx\n", hr);
+    IUnknown_AddRef((IUnknown *)node2);

-        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+    test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);

-        for (i = 0; i < exp_elems[0]; i++)
-        {
-            exp_offset[i] = i;
-            exp_tree_struct[i] = L"P)";
-        }
-        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
-        ok_method_sequence(find_seq4, "find_seq4");
+    for (i = 0; i < exp_elems[0]; i++)
+    {
+        exp_offset[i] = i;
+        exp_tree_struct[i] = L"P)";
     }
+    test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+    ok_method_sequence(find_seq4, "find_seq4");

SafeArrayDestroy(out_req);
     SafeArrayDestroy(offsets);
@@ -8945,7 +8941,7 @@ static void test_UiaFind(void)
     SafeArrayDestroy(offsets);
     SafeArrayDestroy(tree_structs);

-    todo_wine ok(UiaNodeRelease(node2), "UiaNodeRelease returned FALSE\n");
+    ok(UiaNodeRelease(node2), "UiaNodeRelease returned FALSE\n");
     ok(Provider_child.ref == 1, "Unexpected refcnt %ld\n", Provider_child.ref);

initialize_provider_tree();
diff --git a/dlls/uiautomationcore/uia_client.c b/dlls/uiautomationcore/uia_client.c
index 43331108078..364dbc2a97b 100644
--- a/dlls/uiautomationcore/uia_client.c
+++ b/dlls/uiautomationcore/uia_client.c
@@ -968,8 +968,8 @@ exit:
  */
 static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *view_cond,
         struct UiaCondition *search_cond, struct UiaCondition *pre_sibling_nav_stop_cond,
-        struct UiaCondition *ascending_stop_cond, int traversal_opts, BOOL at_root_level, int max_depth, int *cur_depth,
-        HUIANODE *out_node)
+        struct UiaCondition *ascending_stop_cond, int traversal_opts, BOOL at_root_level, BOOL exclude_root,
+        BOOL *root_found, int max_depth, int *cur_depth, HUIANODE *out_node)
 {
     struct uia_node *node = unsafe_impl_from_IWineUiaNode((IWineUiaNode *)huianode);
     BOOL incr_depth = FALSE;
@@ -987,17 +987,22 @@ static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *vi
          * our current depth within the tree.
          */
         incr_depth = TRUE;
-        hr = uia_condition_check(huianode, search_cond);
-        if (FAILED(hr))
-            goto exit;

-        if (uia_condition_matched(hr))
+        if (!(exclude_root && !(*root_found)))
         {
-            IWineUiaNode_AddRef((IWineUiaNode *)huianode);
-            *out_node = huianode;
-            hr = S_FALSE;
-            goto exit;
+            hr = uia_condition_check(huianode, search_cond);
+            if (FAILED(hr))
+                goto exit;
+
+            if (uia_condition_matched(hr))
+            {
+                IWineUiaNode_AddRef((IWineUiaNode *)huianode);
+                *out_node = huianode;
+                hr = S_FALSE;
+                goto exit;
+            }
         }
+        *root_found = TRUE;
     }

if (incr_depth)
@@ -1013,7 +1018,7 @@ static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *vi

if (SUCCEEDED(hr) && node2)
             hr = traverse_uia_node_tree(node2, view_cond, search_cond, pre_sibling_nav_stop_cond, ascending_stop_cond,
-                    traversal_opts, FALSE, max_depth, cur_depth, out_node);
+                    traversal_opts, FALSE, exclude_root, root_found, max_depth, cur_depth, out_node);

if (FAILED(hr) || hr == S_FALSE)
             goto exit;
@@ -1040,7 +1045,7 @@ static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *vi

if (SUCCEEDED(hr) && node2)
         hr = traverse_uia_node_tree(node2, view_cond, search_cond, pre_sibling_nav_stop_cond, ascending_stop_cond,
-                traversal_opts, at_root_level, max_depth, cur_depth, out_node);
+                traversal_opts, at_root_level, exclude_root, root_found, max_depth, cur_depth, out_node);

exit:
     UiaNodeRelease(huianode);
@@ -2745,6 +2750,7 @@ HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, str
     struct uia_node *node = unsafe_impl_from_IWineUiaNode((IWineUiaNode *)huianode);
     SAFEARRAY *runtime_id, *req, *offsets, *tree_structs;
     struct UiaCondition *sibling_stop_cond;
+    BOOL root_found = FALSE;
     int cur_depth = 0;
     BSTR tree_struct;
     HUIANODE node2;
@@ -2764,12 +2770,6 @@ HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, str
         return E_NOTIMPL;
     }

-    if (find_params->ExcludeRoot)
-    {
-        FIXME("ExcludeRoot currently unimplemented.\n");
-        return E_NOTIMPL;
-    }
-
     /*
      * If the initial node has a runtime ID, we'll use it as a stop
      * condition.
@@ -2787,7 +2787,8 @@ HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, str
     node2 = NULL;
     IWineUiaNode_AddRef(&node->IWineUiaNode_iface);
     hr = traverse_uia_node_tree(huianode, cache_req->pViewCondition, find_params->pFindCondition, sibling_stop_cond,
-            cache_req->pViewCondition, TreeTraversalOptions_Default, TRUE, find_params->MaxDepth, &cur_depth, &node2);
+            cache_req->pViewCondition, TreeTraversalOptions_Default, TRUE, find_params->ExcludeRoot, &root_found,
+            find_params->MaxDepth, &cur_depth, &node2);
     if (FAILED(hr) || !node2)
         goto exit;

[PATCH v3 4/5] uiautomationcore: Store traverse_uia_node_tree() results in a dynamic array.

[Connor McAdams]

From: Connor McAdams

Signed-off-by: Connor McAdams 
---
 dlls/uiautomationcore/uia_client.c | 84 ++++++++++++++++++++++++++----
 1 file changed, 73 insertions(+), 11 deletions(-)

diff --git a/dlls/uiautomationcore/uia_client.c b/dlls/uiautomationcore/uia_client.c
index 364dbc2a97b..007b31275cd 100644
--- a/dlls/uiautomationcore/uia_client.c
+++ b/dlls/uiautomationcore/uia_client.c
@@ -25,6 +25,67 @@ WINE_DEFAULT_DEBUG_CHANNEL(uiautomation);

static const struct UiaCondition UiaFalseCondition = { ConditionType_False };

+static BOOL uia_array_reserve(void **elements, SIZE_T *capacity, SIZE_T element_count, SIZE_T element_size)
+{
+    SIZE_T new_capacity, max_capacity;
+    void *new_elements;
+
+    if (element_count <= *capacity)
+        return TRUE;
+
+    max_capacity = ~(SIZE_T)0 / element_size;
+    if (max_capacity < element_count)
+        return FALSE;
+
+    new_capacity = max(*capacity, 4);
+    while (new_capacity < element_count && new_capacity <= max_capacity / 2)
+        new_capacity *= 2;
+
+    if (new_capacity < element_count)
+        new_capacity = max_capacity;
+
+    if (!(new_elements = heap_realloc(*elements, new_capacity * element_size)))
+        return FALSE;
+
+    *elements = new_elements;
+    *capacity = new_capacity;
+    return TRUE;
+}
+
+struct uia_node_array {
+    HUIANODE *nodes;
+    int node_count;
+    SIZE_T node_arr_size;
+};
+
+static void clear_node_array(struct uia_node_array *nodes)
+{
+    if (nodes->nodes)
+    {
+        int i;
+
+        for (i = 0; i < nodes->node_count; i++)
+            UiaNodeRelease(nodes->nodes[i]);
+
+        heap_free(nodes->nodes);
+    }
+
+    memset(nodes, 0, sizeof(*nodes));
+}
+
+static HRESULT add_node_to_node_array(struct uia_node_array *out_nodes, HUIANODE node)
+{
+    if (!uia_array_reserve((void **)&out_nodes->nodes, &out_nodes->node_arr_size, out_nodes->node_count + 1,
+                sizeof(node)))
+        return E_OUTOFMEMORY;
+
+    IWineUiaNode_AddRef((IWineUiaNode *)node);
+    out_nodes->nodes[out_nodes->node_count] = node;
+    out_nodes->node_count++;
+
+    return S_OK;
+}
+
 static HRESULT get_safearray_bounds(SAFEARRAY *sa, LONG *lbound, LONG *elems)
 {
     LONG ubound;
@@ -969,7 +1030,7 @@ exit:
 static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *view_cond,
         struct UiaCondition *search_cond, struct UiaCondition *pre_sibling_nav_stop_cond,
         struct UiaCondition *ascending_stop_cond, int traversal_opts, BOOL at_root_level, BOOL exclude_root,
-        BOOL *root_found, int max_depth, int *cur_depth, HUIANODE *out_node)
+        BOOL *root_found, int max_depth, int *cur_depth, struct uia_node_array *out_nodes)
 {
     struct uia_node *node = unsafe_impl_from_IWineUiaNode((IWineUiaNode *)huianode);
     BOOL incr_depth = FALSE;
@@ -996,8 +1057,10 @@ static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *vi

if (uia_condition_matched(hr))
             {
-                IWineUiaNode_AddRef((IWineUiaNode *)huianode);
-                *out_node = huianode;
+                hr = add_node_to_node_array(out_nodes, huianode);
+                if (FAILED(hr))
+                    goto exit;
+
                 hr = S_FALSE;
                 goto exit;
             }
@@ -1018,7 +1081,7 @@ static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *vi

if (SUCCEEDED(hr) && node2)
             hr = traverse_uia_node_tree(node2, view_cond, search_cond, pre_sibling_nav_stop_cond, ascending_stop_cond,
-                    traversal_opts, FALSE, exclude_root, root_found, max_depth, cur_depth, out_node);
+                    traversal_opts, FALSE, exclude_root, root_found, max_depth, cur_depth, out_nodes);

if (FAILED(hr) || hr == S_FALSE)
             goto exit;
@@ -1045,7 +1108,7 @@ static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *vi

if (SUCCEEDED(hr) && node2)
         hr = traverse_uia_node_tree(node2, view_cond, search_cond, pre_sibling_nav_stop_cond, ascending_stop_cond,
-                traversal_opts, at_root_level, exclude_root, root_found, max_depth, cur_depth, out_node);
+                traversal_opts, at_root_level, exclude_root, root_found, max_depth, cur_depth, out_nodes);

exit:
     UiaNodeRelease(huianode);
@@ -2750,10 +2813,10 @@ HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, str
     struct uia_node *node = unsafe_impl_from_IWineUiaNode((IWineUiaNode *)huianode);
     SAFEARRAY *runtime_id, *req, *offsets, *tree_structs;
     struct UiaCondition *sibling_stop_cond;
+    struct uia_node_array nodes = { 0 };
     BOOL root_found = FALSE;
     int cur_depth = 0;
     BSTR tree_struct;
-    HUIANODE node2;
     HRESULT hr;
     LONG idx;

@@ -2784,12 +2847,11 @@ HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, str
     else
         sibling_stop_cond =  (struct UiaCondition *)&UiaFalseCondition;

-    node2 = NULL;
     IWineUiaNode_AddRef(&node->IWineUiaNode_iface);
     hr = traverse_uia_node_tree(huianode, cache_req->pViewCondition, find_params->pFindCondition, sibling_stop_cond,
             cache_req->pViewCondition, TreeTraversalOptions_Default, TRUE, find_params->ExcludeRoot, &root_found,
-            find_params->MaxDepth, &cur_depth, &node2);
-    if (FAILED(hr) || !node2)
+            find_params->MaxDepth, &cur_depth, &nodes);
+    if (FAILED(hr) || !nodes.node_count)
         goto exit;

if (!(offsets = SafeArrayCreateVector(VT_I4, 0, 1)))
@@ -2804,8 +2866,7 @@ HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, str
         goto exit;
     }

-    hr = UiaGetUpdatedCache(node2, cache_req, NormalizeState_None, NULL, &req, &tree_struct);
-    UiaNodeRelease(node2);
+    hr = UiaGetUpdatedCache(nodes.nodes[0], cache_req, NormalizeState_None, NULL, &req, &tree_struct);
     if (FAILED(hr))
         goto exit;

@@ -2825,6 +2886,7 @@ HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, str

exit:
     VariantClear(&prop_cond.Value);
+    clear_node_array(&nodes);

if (FAILED(hr))
     {

[PATCH v3 5/5] uiautomationcore: Add support for returning multiple HUIANODEs from UiaFind.

[Connor McAdams]

From: Connor McAdams

Signed-off-by: Connor McAdams 
---
 dlls/uiautomationcore/tests/uiautomation.c | 339 ++++++++++-----------
 dlls/uiautomationcore/uia_client.c         | 178 ++++++++---
 2 files changed, 296 insertions(+), 221 deletions(-)

diff --git a/dlls/uiautomationcore/tests/uiautomation.c b/dlls/uiautomationcore/tests/uiautomation.c
index 7275f31f341..28a02fdc14d 100644
--- a/dlls/uiautomationcore/tests/uiautomation.c
+++ b/dlls/uiautomationcore/tests/uiautomation.c
@@ -8712,37 +8712,34 @@ static void test_UiaFind(void)
             AutomationElementMode_Full);
     set_find_params(&find_params, -1, FALSE, FALSE, (struct UiaCondition *)&UiaTrueCondition);
     hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
-    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
-    todo_wine ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);
-    todo_wine ok(Provider_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child.ref);
-    todo_wine ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
-    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
-    todo_wine ok(Provider_child2_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child2_child.ref);
-    todo_wine ok(Provider_child2_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child2_child_child.ref);
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);
+    ok(Provider_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child.ref);
+    ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
+    ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+    ok(Provider_child2_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child2_child.ref);
+    ok(Provider_child2_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child2_child_child.ref);

-    if (SUCCEEDED(hr))
-    {
-        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
-        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child", TRUE);
-        add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child_child", TRUE);
-        add_provider_desc(&exp_node_desc[3], L"Main", L"Provider_child_child2", TRUE);
-        add_provider_desc(&exp_node_desc[4], L"Main", L"Provider_child2", TRUE);
-        add_provider_desc(&exp_node_desc[5], L"Main", L"Provider_child2_child", TRUE);
-        add_provider_desc(&exp_node_desc[6], L"Main", L"Provider_child2_child_child", TRUE);
-        exp_lbound[0] = exp_lbound[1] = 0;
-        exp_elems[0] = 7;
-        exp_elems[1] = 1;
+    add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
+    add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child", TRUE);
+    add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child_child", TRUE);
+    add_provider_desc(&exp_node_desc[3], L"Main", L"Provider_child_child2", TRUE);
+    add_provider_desc(&exp_node_desc[4], L"Main", L"Provider_child2", TRUE);
+    add_provider_desc(&exp_node_desc[5], L"Main", L"Provider_child2_child", TRUE);
+    add_provider_desc(&exp_node_desc[6], L"Main", L"Provider_child2_child_child", TRUE);
+    exp_lbound[0] = exp_lbound[1] = 0;
+    exp_elems[0] = 7;
+    exp_elems[1] = 1;

-        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+    test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);

-        for (i = 0; i < exp_elems[0]; i++)
-        {
-            exp_offset[i] = i;
-            exp_tree_struct[i] = L"P)";
-        }
-        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
-        ok_method_sequence(find_seq1, "find_seq1");
+    for (i = 0; i < exp_elems[0]; i++)
+    {
+        exp_offset[i] = i;
+        exp_tree_struct[i] = L"P)";
     }
+    test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+    ok_method_sequence(find_seq1, "find_seq1");

SafeArrayDestroy(out_req);
     SafeArrayDestroy(offsets);
@@ -8758,31 +8755,28 @@ static void test_UiaFind(void)
             AutomationElementMode_Full);
     set_find_params(&find_params, 1, FALSE, FALSE, (struct UiaCondition *)&UiaTrueCondition);
     hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
-    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
-    todo_wine ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);
-    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
-
-    if (SUCCEEDED(hr))
-    {
-        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
-        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child", TRUE);
-        add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child2", TRUE);
-        exp_lbound[0] = exp_lbound[1] = 0;
-        exp_elems[0] = 3;
-        exp_elems[1] = 1;
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);
+    ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);

-        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+    add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
+    add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child", TRUE);
+    add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child2", TRUE);
+    exp_lbound[0] = exp_lbound[1] = 0;
+    exp_elems[0] = 3;
+    exp_elems[1] = 1;

-        for (i = 0; i < exp_elems[0]; i++)
-        {
-            exp_offset[i] = i;
-            exp_tree_struct[i] = L"P)";
-        }
+    test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);

-        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
-        ok_method_sequence(find_seq2, "find_seq2");
+    for (i = 0; i < exp_elems[0]; i++)
+    {
+        exp_offset[i] = i;
+        exp_tree_struct[i] = L"P)";
     }

+    test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+    ok_method_sequence(find_seq2, "find_seq2");
+
     SafeArrayDestroy(out_req);
     SafeArrayDestroy(offsets);
     SafeArrayDestroy(tree_structs);
@@ -8797,28 +8791,25 @@ static void test_UiaFind(void)
             AutomationElementMode_Full);
     set_find_params(&find_params, 1, FALSE, TRUE, (struct UiaCondition *)&UiaTrueCondition);
     hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
-    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
-    todo_wine ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);
-    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(Provider_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child.ref);
+    ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);

-    if (SUCCEEDED(hr))
-    {
-        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
-        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child2", TRUE);
-        exp_lbound[0] = exp_lbound[1] = 0;
-        exp_elems[0] = 2;
-        exp_elems[1] = 1;
+    add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
+    add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child2", TRUE);
+    exp_lbound[0] = exp_lbound[1] = 0;
+    exp_elems[0] = 2;
+    exp_elems[1] = 1;

-        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+    test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);

-        for (i = 0; i < exp_elems[0]; i++)
-        {
-            exp_offset[i] = i;
-            exp_tree_struct[i] = L"P)";
-        }
-        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
-        ok_method_sequence(find_seq3, "find_seq3");
+    for (i = 0; i < exp_elems[0]; i++)
+    {
+        exp_offset[i] = i;
+        exp_tree_struct[i] = L"P)";
     }
+    test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+    ok_method_sequence(find_seq3, "find_seq3");

SafeArrayDestroy(out_req);
     SafeArrayDestroy(offsets);
@@ -8878,27 +8869,24 @@ static void test_UiaFind(void)
             AutomationElementMode_Full);
     set_find_params(&find_params, 0, FALSE, FALSE, (struct UiaCondition *)&UiaTrueCondition);
     hr = UiaFind(node2, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
-    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
-    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);

-    if (SUCCEEDED(hr))
-    {
-        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
-        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child2", TRUE);
-        exp_lbound[0] = exp_lbound[1] = 0;
-        exp_elems[0] = 2;
-        exp_elems[1] = 1;
+    add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
+    add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child2", TRUE);
+    exp_lbound[0] = exp_lbound[1] = 0;
+    exp_elems[0] = 2;
+    exp_elems[1] = 1;

-        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+    test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);

-        for (i = 0; i < exp_elems[0]; i++)
-        {
-            exp_offset[i] = i;
-            exp_tree_struct[i] = L"P)";
-        }
-        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
-        ok_method_sequence(find_seq5, "find_seq5");
+    for (i = 0; i < exp_elems[0]; i++)
+    {
+        exp_offset[i] = i;
+        exp_tree_struct[i] = L"P)";
     }
+    test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+    ok_method_sequence(find_seq5, "find_seq5");

SafeArrayDestroy(out_req);
     SafeArrayDestroy(offsets);
@@ -8918,24 +8906,21 @@ static void test_UiaFind(void)
             AutomationElementMode_Full);
     set_find_params(&find_params, 0, FALSE, FALSE, (struct UiaCondition *)&UiaTrueCondition);
     hr = UiaFind(node2, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
-    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);

-    if (SUCCEEDED(hr))
-    {
-        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
-        exp_lbound[0] = exp_lbound[1] = 0;
-        exp_elems[0] = exp_elems[1] = 1;
+    add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child", TRUE);
+    exp_lbound[0] = exp_lbound[1] = 0;
+    exp_elems[0] = exp_elems[1] = 1;

-        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+    test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);

-        for (i = 0; i < exp_elems[0]; i++)
-        {
-            exp_offset[i] = i;
-            exp_tree_struct[i] = L"P)";
-        }
-        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
-        ok_method_sequence(find_seq6, "find_seq6");
+    for (i = 0; i < exp_elems[0]; i++)
+    {
+        exp_offset[i] = i;
+        exp_tree_struct[i] = L"P)";
     }
+    test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+    ok_method_sequence(find_seq6, "find_seq6");

SafeArrayDestroy(out_req);
     SafeArrayDestroy(offsets);
@@ -8973,31 +8958,28 @@ static void test_UiaFind(void)
             AutomationElementMode_Full);
     set_find_params(&find_params, 1, FALSE, FALSE, (struct UiaCondition *)&prop_cond[1]);
     hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
-    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
-    todo_wine ok(Provider_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child.ref);
-    todo_wine ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
-    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(Provider_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child.ref);
+    ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
+    ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);

-    if (SUCCEEDED(hr))
-    {
-        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
-        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child_child", TRUE);
-        add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child_child2", TRUE);
-        add_provider_desc(&exp_node_desc[3], L"Main", L"Provider_child2", TRUE);
-        exp_lbound[0] = exp_lbound[1] = 0;
-        exp_elems[0] = 4;
-        exp_elems[1] = 1;
+    add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
+    add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child_child", TRUE);
+    add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child_child2", TRUE);
+    add_provider_desc(&exp_node_desc[3], L"Main", L"Provider_child2", TRUE);
+    exp_lbound[0] = exp_lbound[1] = 0;
+    exp_elems[0] = 4;
+    exp_elems[1] = 1;

-        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+    test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);

-        for (i = 0; i < exp_elems[0]; i++)
-        {
-            exp_offset[i] = i;
-            exp_tree_struct[i] = L"P)";
-        }
-        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
-        ok_method_sequence(find_seq7, "find_seq7");
+    for (i = 0; i < exp_elems[0]; i++)
+    {
+        exp_offset[i] = i;
+        exp_tree_struct[i] = L"P)";
     }
+    test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+    ok_method_sequence(find_seq7, "find_seq7");

SafeArrayDestroy(out_req);
     SafeArrayDestroy(offsets);
@@ -9029,41 +9011,38 @@ static void test_UiaFind(void)
             AutomationElementMode_Full);
     set_find_params(&find_params, 1, FALSE, FALSE, (struct UiaCondition *)&prop_cond[1]);
     hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
-    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
-    todo_wine ok(Provider_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child.ref);
-    todo_wine ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
-    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(Provider_child_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child.ref);
+    ok(Provider_child_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child_child2.ref);
+    ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);

-    if (SUCCEEDED(hr))
-    {
-        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
-        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child_child", TRUE);
-        add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child_child2", TRUE);
-        add_provider_desc(&exp_node_desc[3], L"Main", L"Provider_child2", TRUE);
-        exp_lbound[0] = exp_lbound[1] = 0;
-        exp_elems[0] = 4;
-        exp_elems[1] = 1;
+    add_provider_desc(&exp_node_desc[0], L"Main", L"Provider", TRUE);
+    add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child_child", TRUE);
+    add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child_child2", TRUE);
+    add_provider_desc(&exp_node_desc[3], L"Main", L"Provider_child2", TRUE);
+    exp_lbound[0] = exp_lbound[1] = 0;
+    exp_elems[0] = 4;
+    exp_elems[1] = 1;

-        idx[0] = 2;
-        idx[1] = 0;
-        hr = SafeArrayGetElement(out_req, idx, &v);
-        ok(hr == S_OK, "Unexpected hr %#lx\n", hr);
+    idx[0] = 2;
+    idx[1] = 0;
+    hr = SafeArrayGetElement(out_req, idx, &v);
+    ok(hr == S_OK, "Unexpected hr %#lx\n", hr);

-        /* node2 is now set as Provider_child_child2. */
-        hr = UiaHUiaNodeFromVariant(&v, &node2);
-        ok(hr == S_OK, "Unexpected hr %#lx\n", hr);
-        IUnknown_AddRef((IUnknown *)node2);
+    /* node2 is now set as Provider_child_child2. */
+    hr = UiaHUiaNodeFromVariant(&v, &node2);
+    ok(hr == S_OK, "Unexpected hr %#lx\n", hr);
+    IUnknown_AddRef((IUnknown *)node2);

-        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+    test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);

-        for (i = 0; i < exp_elems[0]; i++)
-        {
-            exp_offset[i] = i;
-            exp_tree_struct[i] = L"P)";
-        }
-        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
-        ok_method_sequence(find_seq8, "find_seq8");
+    for (i = 0; i < exp_elems[0]; i++)
+    {
+        exp_offset[i] = i;
+        exp_tree_struct[i] = L"P)";
     }
+    test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+    ok_method_sequence(find_seq8, "find_seq8");

SafeArrayDestroy(out_req);
     SafeArrayDestroy(offsets);
@@ -9099,29 +9078,26 @@ static void test_UiaFind(void)
             AutomationElementMode_Full);
     set_find_params(&find_params, 1, FALSE, FALSE, (struct UiaCondition *)&prop_cond[1]);
     hr = UiaFind(node2, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
-    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
-    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
-    todo_wine ok(Provider_child2_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child2_child.ref);
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
+    ok(Provider_child2_child.ref == 2, "Unexpected refcnt %ld\n", Provider_child2_child.ref);

-    if (SUCCEEDED(hr))
-    {
-        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child_child2", TRUE);
-        add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child2", TRUE);
-        add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child2_child", TRUE);
-        exp_lbound[0] = exp_lbound[1] = 0;
-        exp_elems[0] = 3;
-        exp_elems[1] = 1;
+    add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child_child2", TRUE);
+    add_provider_desc(&exp_node_desc[1], L"Main", L"Provider_child2", TRUE);
+    add_provider_desc(&exp_node_desc[2], L"Main", L"Provider_child2_child", TRUE);
+    exp_lbound[0] = exp_lbound[1] = 0;
+    exp_elems[0] = 3;
+    exp_elems[1] = 1;

-        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+    test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);

-        for (i = 0; i < exp_elems[0]; i++)
-        {
-            exp_offset[i] = i;
-            exp_tree_struct[i] = L"P)";
-        }
-        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
-        ok_method_sequence(find_seq9, "find_seq9");
+    for (i = 0; i < exp_elems[0]; i++)
+    {
+        exp_offset[i] = i;
+        exp_tree_struct[i] = L"P)";
     }
+    test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+    ok_method_sequence(find_seq9, "find_seq9");

SafeArrayDestroy(out_req);
     SafeArrayDestroy(offsets);
@@ -9131,7 +9107,7 @@ static void test_UiaFind(void)
     for (i = 0; i < ARRAY_SIZE(exp_node_desc); i++)
         init_node_provider_desc(&exp_node_desc[i], GetCurrentProcessId(), NULL);

-    todo_wine ok(UiaNodeRelease(node2), "UiaNodeRelease returned FALSE\n");
+    ok(UiaNodeRelease(node2), "UiaNodeRelease returned FALSE\n");
     ok(Provider_child_child2.ref == 1, "Unexpected refcnt %ld\n", Provider_child_child2.ref);

/*
@@ -9157,27 +9133,24 @@ static void test_UiaFind(void)
             AutomationElementMode_Full);
     set_find_params(&find_params, 1, FALSE, TRUE, (struct UiaCondition *)&prop_cond[1]);
     hr = UiaFind(node, &find_params, &cache_req, &out_req, &offsets, &tree_structs);
-    todo_wine ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
-    todo_wine ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);
-
-    if (SUCCEEDED(hr))
-    {
-        add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child2", TRUE);
-        exp_lbound[0] = exp_lbound[1] = 0;
-        exp_elems[0] = 1;
-        exp_elems[1] = 1;
+    ok(hr == S_OK, "Unexpected hr %#lx.\n", hr);
+    ok(Provider_child2.ref == 2, "Unexpected refcnt %ld\n", Provider_child2.ref);

-        test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);
+    add_provider_desc(&exp_node_desc[0], L"Main", L"Provider_child2", TRUE);
+    exp_lbound[0] = exp_lbound[1] = 0;
+    exp_elems[0] = 1;
+    exp_elems[1] = 1;

-        for (i = 0; i < exp_elems[0]; i++)
-        {
-            exp_offset[i] = i;
-            exp_tree_struct[i] = L"P)";
-        }
-        test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+    test_cache_req_sa(out_req, exp_lbound, exp_elems, exp_node_desc);

-        ok_method_sequence(find_seq10, "find_seq10");
+    for (i = 0; i < exp_elems[0]; i++)
+    {
+        exp_offset[i] = i;
+        exp_tree_struct[i] = L"P)";
     }
+    test_find_sa_results(tree_structs, offsets, exp_elems[0], exp_tree_struct, exp_offset);
+
+    ok_method_sequence(find_seq10, "find_seq10");

SafeArrayDestroy(out_req);
     SafeArrayDestroy(offsets);
diff --git a/dlls/uiautomationcore/uia_client.c b/dlls/uiautomationcore/uia_client.c
index 007b31275cd..8fecdd2fbcb 100644
--- a/dlls/uiautomationcore/uia_client.c
+++ b/dlls/uiautomationcore/uia_client.c
@@ -86,25 +86,17 @@ static HRESULT add_node_to_node_array(struct uia_node_array *out_nodes, HUIANODE
     return S_OK;
 }

-static HRESULT get_safearray_bounds(SAFEARRAY *sa, LONG *lbound, LONG *elems)
+static HRESULT get_safearray_dim_bounds(SAFEARRAY *sa, UINT dim, LONG *lbound, LONG *elems)
 {
     LONG ubound;
     HRESULT hr;
-    UINT dims;

*lbound = *elems = 0;
-    dims = SafeArrayGetDim(sa);
-    if (dims != 1)
-    {
-        WARN("Invalid dimensions %d for safearray.\n", dims);
-        return E_FAIL;
-    }
-
-    hr = SafeArrayGetLBound(sa, 1, lbound);
+    hr = SafeArrayGetLBound(sa, dim, lbound);
     if (FAILED(hr))
         return hr;

-    hr = SafeArrayGetUBound(sa, 1, &ubound);
+    hr = SafeArrayGetUBound(sa, dim, &ubound);
     if (FAILED(hr))
         return hr;

@@ -112,6 +104,21 @@ static HRESULT get_safearray_bounds(SAFEARRAY *sa, LONG *lbound, LONG *elems)
     return S_OK;
 }

+static HRESULT get_safearray_bounds(SAFEARRAY *sa, LONG *lbound, LONG *elems)
+{
+    UINT dims;
+
+    *lbound = *elems = 0;
+    dims = SafeArrayGetDim(sa);
+    if (dims != 1)
+    {
+        WARN("Invalid dimensions %d for safearray.\n", dims);
+        return E_FAIL;
+    }
+
+    return get_safearray_dim_bounds(sa, 1, lbound, elems);
+}
+
 int uia_compare_safearrays(SAFEARRAY *sa1, SAFEARRAY *sa2, int prop_type)
 {
     LONG i, idx, lbound[2], elems[2];
@@ -1030,7 +1037,7 @@ exit:
 static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *view_cond,
         struct UiaCondition *search_cond, struct UiaCondition *pre_sibling_nav_stop_cond,
         struct UiaCondition *ascending_stop_cond, int traversal_opts, BOOL at_root_level, BOOL exclude_root,
-        BOOL *root_found, int max_depth, int *cur_depth, struct uia_node_array *out_nodes)
+        BOOL *root_found, BOOL find_first, int max_depth, int *cur_depth, struct uia_node_array *out_nodes)
 {
     struct uia_node *node = unsafe_impl_from_IWineUiaNode((IWineUiaNode *)huianode);
     BOOL incr_depth = FALSE;
@@ -1061,8 +1068,11 @@ static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *vi
                 if (FAILED(hr))
                     goto exit;

-                hr = S_FALSE;
-                goto exit;
+                if (find_first)
+                {
+                    hr = S_FALSE;
+                    goto exit;
+                }
             }
         }
         *root_found = TRUE;
@@ -1081,7 +1091,7 @@ static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *vi

if (SUCCEEDED(hr) && node2)
             hr = traverse_uia_node_tree(node2, view_cond, search_cond, pre_sibling_nav_stop_cond, ascending_stop_cond,
-                    traversal_opts, FALSE, exclude_root, root_found, max_depth, cur_depth, out_nodes);
+                    traversal_opts, FALSE, exclude_root, root_found, find_first, max_depth, cur_depth, out_nodes);

if (FAILED(hr) || hr == S_FALSE)
             goto exit;
@@ -1108,7 +1118,7 @@ static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *vi

if (SUCCEEDED(hr) && node2)
         hr = traverse_uia_node_tree(node2, view_cond, search_cond, pre_sibling_nav_stop_cond, ascending_stop_cond,
-                traversal_opts, at_root_level, exclude_root, root_found, max_depth, cur_depth, out_nodes);
+                traversal_opts, at_root_level, exclude_root, root_found, find_first, max_depth, cur_depth, out_nodes);

exit:
     UiaNodeRelease(huianode);
@@ -2803,6 +2813,50 @@ HRESULT WINAPI UiaNavigate(HUIANODE huianode, enum NavigateDirection dir, struct
     return hr;
 }

+/* Combine multiple cache requests into a single SAFEARRAY. */
+static HRESULT uia_cache_request_combine(SAFEARRAY **reqs, int reqs_count, SAFEARRAY *out_req)
+{
+    LONG idx[2], lbound[2], elems[2], cur_offset;
+    int i, x, y;
+    HRESULT hr;
+    VARIANT v;
+
+    for (i = cur_offset = 0; i < reqs_count; i++)
+    {
+        if (!reqs[i])
+            continue;
+
+        for (x = 0; x < 2; x++)
+        {
+            hr = get_safearray_dim_bounds(reqs[i], 1 + x, &lbound[x], &elems[x]);
+            if (FAILED(hr))
+                return hr;
+        }
+
+        for (x = 0; x < elems[0]; x++)
+        {
+            for (y = 0; y < elems[1]; y++)
+            {
+                idx[0] = x + lbound[0];
+                idx[1] = y + lbound[1];
+                hr = SafeArrayGetElement(reqs[i], idx, &v);
+                if (FAILED(hr))
+                    return hr;
+
+                idx[0] = x + cur_offset;
+                idx[1] = y;
+                hr = SafeArrayPutElement(out_req, idx, &v);
+                if (FAILED(hr))
+                    return hr;
+            }
+        }
+
+        cur_offset += elems[0];
+    }
+
+    return S_OK;
+}
+
 /***********************************************************************
  *          UiaFind (uiautomationcore.@)
  */
@@ -2811,14 +2865,15 @@ HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, str
 {
     struct UiaPropertyCondition prop_cond = { ConditionType_Property, UIA_RuntimeIdPropertyId };
     struct uia_node *node = unsafe_impl_from_IWineUiaNode((IWineUiaNode *)huianode);
-    SAFEARRAY *runtime_id, *req, *offsets, *tree_structs;
+    SAFEARRAY *runtime_id, *req, *offsets, *tree_structs, **tmp_reqs;
     struct UiaCondition *sibling_stop_cond;
     struct uia_node_array nodes = { 0 };
+    LONG idx, lbound, elems, cur_offset;
+    SAFEARRAYBOUND sabound[2];
     BOOL root_found = FALSE;
-    int cur_depth = 0;
+    int i, cur_depth = 0;
     BSTR tree_struct;
     HRESULT hr;
-    LONG idx;

TRACE("(%p, %p, %p, %p, %p, %p)\n", huianode, find_params, cache_req, out_req, out_offsets, out_tree_structs);

@@ -2826,12 +2881,7 @@ HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, str
         return E_INVALIDARG;

*out_tree_structs = *out_offsets = *out_req = tree_structs = offsets = req = NULL;
-
-    if (!find_params->FindFirst)
-    {
-        FIXME("Finding more than one HUIANODE is currently unimplemented.\n");
-        return E_NOTIMPL;
-    }
+    tmp_reqs = NULL;

/*
      * If the initial node has a runtime ID, we'll use it as a stop
@@ -2850,35 +2900,80 @@ HRESULT WINAPI UiaFind(HUIANODE huianode, struct UiaFindParams *find_params, str
     IWineUiaNode_AddRef(&node->IWineUiaNode_iface);
     hr = traverse_uia_node_tree(huianode, cache_req->pViewCondition, find_params->pFindCondition, sibling_stop_cond,
             cache_req->pViewCondition, TreeTraversalOptions_Default, TRUE, find_params->ExcludeRoot, &root_found,
-            find_params->MaxDepth, &cur_depth, &nodes);
+            find_params->FindFirst, find_params->MaxDepth, &cur_depth, &nodes);
     if (FAILED(hr) || !nodes.node_count)
         goto exit;

-    if (!(offsets = SafeArrayCreateVector(VT_I4, 0, 1)))
+    if (!(offsets = SafeArrayCreateVector(VT_I4, 0, nodes.node_count)))
     {
         hr = E_FAIL;
         goto exit;
     }

-    if (!(tree_structs = SafeArrayCreateVector(VT_BSTR, 0, 1)))
+    if (!(tree_structs = SafeArrayCreateVector(VT_BSTR, 0, nodes.node_count)))
     {
         hr = E_FAIL;
         goto exit;
     }

-    hr = UiaGetUpdatedCache(nodes.nodes[0], cache_req, NormalizeState_None, NULL, &req, &tree_struct);
-    if (FAILED(hr))
+    if (!(tmp_reqs = heap_alloc_zero(sizeof(*tmp_reqs) * nodes.node_count)))
+    {
+        hr = E_OUTOFMEMORY;
         goto exit;
+    }

-    idx = 0;
-    hr = SafeArrayPutElement(tree_structs, &idx, tree_struct);
-    SysFreeString(tree_struct);
-    if (FAILED(hr))
-        goto exit;
+    /*
+     * Get a count of how many total nodes we'll need to return, as well as
+     * set the tree structure strings and cache request offsets for our final
+     * combined SAFEARRAY.
+     */
+    for (i = cur_offset = 0; i < nodes.node_count; i++)
+    {
+        hr = UiaGetUpdatedCache(nodes.nodes[i], cache_req, NormalizeState_None, NULL, &tmp_reqs[i], &tree_struct);
+        if (FAILED(hr))
+            goto exit;

-    hr = SafeArrayPutElement(offsets, &idx, &idx);
-    if (FAILED(hr))
-        goto exit;
+        idx = i;
+        hr = SafeArrayPutElement(tree_structs, &idx, tree_struct);
+        SysFreeString(tree_struct);
+        if (FAILED(hr))
+            goto exit;
+
+        hr = SafeArrayPutElement(offsets, &idx, &cur_offset);
+        if (FAILED(hr))
+            goto exit;
+
+        if (!tmp_reqs[i])
+            continue;
+
+        hr = get_safearray_dim_bounds(tmp_reqs[i], 1, &lbound, &elems);
+        if (FAILED(hr))
+            goto exit;
+
+        cur_offset += elems;
+    }
+
+    if (nodes.node_count == 1)
+    {
+        req = tmp_reqs[0];
+        heap_free(tmp_reqs);
+        tmp_reqs = NULL;
+    }
+    else
+    {
+        sabound[0].lLbound = sabound[1].lLbound = 0;
+        sabound[0].cElements = cur_offset;
+        sabound[1].cElements = 1 + cache_req->cProperties + cache_req->cPatterns;
+        if (!(req = SafeArrayCreate(VT_VARIANT, 2, sabound)))
+        {
+            hr = E_FAIL;
+            goto exit;
+        }
+
+        hr = uia_cache_request_combine(tmp_reqs, nodes.node_count, req);
+        if (FAILED(hr))
+            goto exit;
+    }

*out_tree_structs = tree_structs;
     *out_offsets = offsets;
@@ -2888,6 +2983,13 @@ exit:
     VariantClear(&prop_cond.Value);
     clear_node_array(&nodes);

+    if (tmp_reqs)
+    {
+        for (i = 0; i < nodes.node_count; i++)
+            SafeArrayDestroy(tmp_reqs[i]);
+        heap_free(tmp_reqs);
+    }
+
     if (FAILED(hr))
     {
         SafeArrayDestroy(tree_structs);

[Connor McAdams (＠cmcadams)]

On Fri Nov 11 18:58:02 2022 +0000, Connor McAdams wrote:
> changed this line in [version 3 of the diff](/wine/wine/-/merge_requests/1249/diffs?diff_id=18228&start_sha=b53b43af0dcc9547a9fca1a077afeb050cf21706#757856e6ad8b0244e53744faeb8594b6ec93b002_8629_8658)

I've changed this now to functions for each assignment, which should explain the tree structure programmatically rather than in a code comment, which should help to prevent inconsistencies.

[Connor McAdams (＠cmcadams)]

V3:
- Change tree structure assignments in tests so that the tree structure is expressed through function assignment rather than code comments.
- Rename `get_sibling_node_for_tree` to `traverse_uia_node_tree_siblings` and attempt to improve comments to further clarify the functions purpose.

[Connor McAdams (＠cmcadams)]

On Fri Nov 11 18:55:46 2022 +0000, Esme Povirk wrote:
> Just an update for anyone following here: we had an in-depth discussion.
> I think it makes sense to me now, and we have a plan for how to explain it.

This should be improved in V3, although I'm not sure I want to mark this as resolved until it's agreed upon that the changes I've made resolve this.

[Esme Povirk (＠madewokherd)]

Esme Povirk (@madewokherd) commented about dlls/uiautomationcore/tests/uiautomation.c:
> - SAFEARRAY *out_req, *offsets, *tree_structs;
> - struct node_provider_desc exp_node_desc[7];
> - struct UiaPropertyCondition prop_cond[2];
> - struct UiaCacheRequest cache_req;
> - struct UiaFindParams find_params;
> - const WCHAR *exp_tree_struct[7];
> - HUIANODE node, node2;
> - int exp_offset[6];
> - HRESULT hr;
> - VARIANT v;
> -
> - CoInitializeEx(NULL, COINIT_MULTITHREADED);
> -
> - set_provider_root_and_parent(&Provider, &Provider, NULL);
> - set_provider_children(&Provider, &Provider_child, &Provider_child2);
> - set_provider_siblings(&Provider, NULL, NULL);

This is still including each individual link which seems redundant and potentially inconsistent. What I had in mind was an add_child function that would update the parent's last_child link, the parent's first_child link if necessary, the child's parent link, the child's previous_sibling link if necessary, and the previous sibling's next_sibling link.

[Connor McAdams (＠cmcadams)]

On Fri Nov 11 19:12:13 2022 +0000, Esme Povirk wrote:
> This is still including each individual link which seems redundant and
> potentially inconsistent. What I had in mind was an add_child function
> that would update the parent's last_child link, the parent's first_child
> link if necessary, the child's parent link, the child's previous_sibling
> link if necessary, and the previous sibling's next_sibling link.

Ah, yes that is a much better idea. So setting a provider as a child also sets the parent link for the children. Since we're only dealing with two children at most in this tree, we could also set siblings in that same function.

[Esme Povirk (＠madewokherd)]

On Fri Nov 11 19:15:54 2022 +0000, Connor McAdams wrote:
> Ah, yes that is a much better idea. So setting a provider as a child
> also sets the parent link for the children. Since we're only dealing
> with two children at most in this tree, we could also set siblings in
> that same function.

I think in practice if you can handle 2 children this way, you can handle many children.

[Esme Povirk (＠madewokherd)]

On Fri Nov 11 19:17:33 2022 +0000, Esme Povirk wrote:
> I think in practice if you can handle 2 children this way, you can
> handle many children.

I was thinking something like this would work:
```
add_child(parent, child):
    prev_last_child = parent->last_child
    parent->last_child = child
    child->parent = parent
    if (prev_last_child):
        prev_last_child->next_sibling = child
        child->prev_sibling = prev_last_child
    else:
        parent->first_child = child
```

But it now occurs to me that you could special-case it to only handle up to 2 children.

[Esme Povirk (＠madewokherd)]

Esme Povirk (@madewokherd) commented about dlls/uiautomationcore/uia_client.c:
> -
> * huianode doesn't match our stop condition.
> -
> */
> - hr = uia_condition_check(huianode, pre_sibling_nav_stop_cond);
> - if (FAILED(hr) || uia_condition_matched(hr))
> -
>    goto exit;
> -
> - /* Now, check for any siblings to visit. */
> - if (traversal_opts & TreeTraversalOptions_LastToFirstOrder)
> -
>    hr = traverse_uia_node_tree_siblings(huianode, ascending_stop_cond, NavigateDirection_PreviousSibling,
> -
>            at_root_level, &node2);
> - else
> -
>    hr = traverse_uia_node_tree_siblings(huianode, ascending_stop_cond, NavigateDirection_NextSibling,
> -
>            at_root_level, &node2);
> -
> - if (SUCCEEDED(hr) && node2)
> -
>    hr = traverse_uia_node_tree(node2, view_cond, search_cond, pre_sibling_nav_stop_cond, ascending_stop_cond,

I think it would be worth manually tail-call-optimizing this so we don't need a stack frame for every sibling we traverse (basically reassign node and go back to start). Maybe convert the whole thing to a loop of some sort?

[Esme Povirk (＠madewokherd)]

Esme Povirk (@madewokherd) commented about dlls/uiautomationcore/uia_client.c:
> */
>  static HRESULT traverse_uia_node_tree(HUIANODE huianode, struct UiaCondition *view_cond,
>          struct UiaCondition *search_cond, struct UiaCondition *pre_sibling_nav_stop_cond,
> -
>    struct UiaCondition *ascending_stop_cond, int traversal_opts, BOOL at_root_level, int max_depth, int *cur_depth,
> -
>    HUIANODE *out_node)
> -
>    struct UiaCondition *ascending_stop_cond, int traversal_opts, BOOL at_root_level, BOOL exclude_root,
> -
>    BOOL *root_found, int max_depth, int *cur_depth, HUIANODE *out_node)

I think this can be reduced to a single argument, with *root_found starting out as FALSE if exclude_root is FALSE.

[Esme Povirk (＠madewokherd)]

Esme Povirk (@madewokherd) commented about dlls/uiautomationcore/uia_client.c:
> - SIZE_T new_capacity, max_capacity;
> - void *new_elements;
> -
> - if (element_count <= *capacity)
> -
>    return TRUE;
> -
> - max_capacity = ~(SIZE_T)0 / element_size;
> - if (max_capacity < element_count)
> -
>    return FALSE;
> -
> - new_capacity = max(*capacity, 4);
> - while (new_capacity < element_count && new_capacity <= max_capacity / 2)
> -
>    new_capacity *= 2;
> -
> - if (new_capacity < element_count)
> -
>    new_capacity = max_capacity;

I'm not sure I fully understand this bit. I feel like the end result (assuming you're not starting from 0) is going to be `new_capacity = *capacity * 2`, or just `new_capacity = element_count` if that's too small. But maybe I'm missing something.

[Esme Povirk (＠madewokherd)]

On Fri Nov 11 20:47:36 2022 +0000, Esme Povirk wrote:
> I'm not sure I fully understand this bit. I feel like the end result
> (assuming you're not starting from 0) is going to be `new_capacity =
> *capacity * 2`, or just `new_capacity = element_count` if that's too
> small. But maybe I'm missing something.

Oh actually, I really don't get it. When would you *ever* want to allocate max_capacity?

[Connor McAdams (＠cmcadams)]

On Fri Nov 11 20:51:53 2022 +0000, Esme Povirk wrote:
> Oh actually, I really don't get it. When would you *ever* want to
> allocate max_capacity?

This same function body is used in multiple places, just with different function names in each. A few examples are:

- `dlls/d3d10/effect.c`: d3d_array_reserve()
- `dlls/wined3d/utils.c`: wined3d_array_reserve()
- `dlls/d2d1/d2d1_private.h`: d2d_array_reserve()

I've just reused/renamed it. So I'm _assuming_ there was some reason behind the design decisions, but I myself didn't make them.

[Esme Povirk (＠madewokherd)]

On Fri Nov 11 20:54:18 2022 +0000, Connor McAdams wrote:
> This same function body is used in multiple places, just with different
> function names in each. A few examples are:
> - `dlls/d3d10/effect.c`: d3d_array_reserve()
> - `dlls/wined3d/utils.c`: wined3d_array_reserve()
> - `dlls/d2d1/d2d1_private.h`: d2d_array_reserve()
>
> I've just reused/renamed it. So I'm _assuming_ there was some reason
> behind the design decisions, but I myself didn't make them.

I think it might have been copied incorrectly when it was added to d2d? Line 45 here should be `new_capacity = element_count` to match what's in d3d10 and wined3d.

[Zebediah Figura (＠zfigura)]

On Fri Nov 11 21:16:19 2022 +0000, Esme Povirk wrote:
> I think it might have been copied incorrectly when it was added to d2d?
> Line 45 here should be `new_capacity = element_count` to match what's in
> d3d10 and wined3d.

The point of that part, as far as I can tell, is to handle integer overflow without incorrectly allocating something too small. I think we expect the allocation to fail either way at that point, but that aside, arguably the wined3d version is better, and it looks like it's actually the newer one.