[PATCH v9 1/2] widl: Prevent infinite loop when structure contains array of itself

[Fabian Maurer]

From: Fabian Maurer

Wine-Bug: https://bugs.winehq.org/show_bug.cgi?id=55115
---
 tools/widl/typegen.c | 77 ++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 70 insertions(+), 7 deletions(-)

diff --git a/tools/widl/typegen.c b/tools/widl/typegen.c
index 23db6555e9d..c90cf6b7cf9 100644
--- a/tools/widl/typegen.c
+++ b/tools/widl/typegen.c
@@ -745,8 +745,41 @@ static int type_has_pointers(const type_t *type)
     return FALSE;
 }

-static int type_has_full_pointer(const type_t *type, const attr_list_t *attrs,
-                                 int toplevel_param)
+struct visited_struct_array
+{
+    const type_t **structs;
+    unsigned int count;
+    unsigned int capacity;
+};
+
+static inline int array_reserve(void **elements, size_t *capacity, size_t count, size_t size)
+{
+    size_t new_capacity, max_capacity;
+    void *new_elements;
+
+    if (count <= *capacity)
+        return TRUE;
+
+    max_capacity = ~(size_t)0 / size;
+    if (count > max_capacity)
+        return FALSE;
+
+    new_capacity = max(4, *capacity);
+    while (new_capacity < count && new_capacity <= max_capacity / 2)
+        new_capacity *= 2;
+    if (new_capacity < count)
+        new_capacity = max_capacity;
+
+    if (!(new_elements = realloc(*elements, new_capacity * size)))
+        return FALSE;
+
+    *elements = new_elements;
+    *capacity = new_capacity;
+    return TRUE;
+}
+
+static int type_has_full_pointer_recurse(const type_t *type, const attr_list_t *attrs,
+                                 int toplevel_param, struct visited_struct_array *visited_structs)
 {
     switch (typegen_detect_type(type, NULL, TDT_IGNORE_STRINGS))
     {
@@ -761,17 +794,38 @@ static int type_has_full_pointer(const type_t *type, const attr_list_t *attrs,
         if (get_pointer_fc(type, attrs, toplevel_param) == FC_FP)
             return TRUE;
         else
-            return type_has_full_pointer(type_array_get_element_type(type), NULL, FALSE);
+            return type_has_full_pointer_recurse(type_array_get_element_type(type), NULL, FALSE, visited_structs);
     case TGT_STRUCT:
     {
+        unsigned int i;
+        int ret = FALSE;
         var_list_t *fields = type_struct_get_fields(type);
         const var_t *field;
+
+        for (i = 0; i < visited_structs->count; i++)
+        {
+            if (visited_structs->structs[i] == type)
+            {
+                /* Found struct we visited already, abort to prevent infinite loop.
+                 * Can't be at the first struct we visit, so we can skip cleanup and just return */
+               return FALSE;
+            }
+        }
+
+        array_reserve((void**)&visited_structs->structs, &visited_structs->capacity, visited_structs->count + 1, sizeof(struct type_t*));
+        visited_structs->structs[visited_structs->count] = type;
+
+        visited_structs->count++;
         if (fields) LIST_FOR_EACH_ENTRY( field, fields, const var_t, entry )
         {
-            if (type_has_full_pointer(field->declspec.type, field->attrs, FALSE))
-                return TRUE;
+            if (type_has_full_pointer_recurse(field->declspec.type, field->attrs, FALSE, visited_structs))
+            {
+                ret = TRUE;
+                break;
+            }
         }
-        break;
+        visited_structs->count--;
+        return ret;
     }
     case TGT_UNION:
     {
@@ -780,7 +834,7 @@ static int type_has_full_pointer(const type_t *type, const attr_list_t *attrs,
         fields = type_union_get_cases(type);
         if (fields) LIST_FOR_EACH_ENTRY( field, fields, const var_t, entry )
         {
-            if (field->declspec.type && type_has_full_pointer(field->declspec.type, field->attrs, FALSE))
+            if (field->declspec.type && type_has_full_pointer_recurse(field->declspec.type, field->attrs, FALSE, visited_structs))
                 return TRUE;
         }
         break;
@@ -799,6 +853,15 @@ static int type_has_full_pointer(const type_t *type, const attr_list_t *attrs,
     return FALSE;
 }

+static int type_has_full_pointer(const type_t *type, const attr_list_t *attrs, int toplevel_param)
+{
+    int ret;
+    struct visited_struct_array visited_structs = {0};
+    ret = type_has_full_pointer_recurse(type, attrs, toplevel_param, &visited_structs);
+    free(visited_structs.structs);
+    return ret;
+}
+
 static unsigned short user_type_offset(const char *name)
 {
     user_type_t *ut;