gdb

	PR python/10676:
	* python/py-type.c: Include bcache.h, vec.h.
	(struct type_equality_entry): New.
	(compare_strings): New function.
	(check_types_equal): Likewise.
	(check_types_worklist): Likewise.
	(typy_richcompare): Likewise.
	(type_object_type): Set tp_richcompare field.
gdb/testsuite
	PR python/10676:
	* gdb.python/py-type.exp (test_fields): Add tests for type
	equality.

1 files changed, 197 insertions, 1 deletions

diff --git a/gdb/python/py-type.c b/gdb/python/py-type.c
index b3043109632..4c80210861f 100644
--- a/gdb/python/py-type.c
+++ b/gdb/python/py-type.c
@@ -27,6 +27,8 @@
 #include "demangle.h"
 #include "objfiles.h"
 #include "language.h"
+#include "vec.h"
+#include "bcache.h"
 
 typedef struct pyty_type_object
 {
@@ -721,6 +723,200 @@ typy_str (PyObject *self)
   return result;
 }
 
+/* An entry in the type-equality bcache.  */
+
+typedef struct type_equality_entry
+{
+  struct type *type1, *type2;
+} type_equality_entry_d;
+
+DEF_VEC_O (type_equality_entry_d);
+
+/* A helper function to compare two strings.  Returns 1 if they are
+   the same, 0 otherwise.  Handles NULLs properly.  */
+
+static int
+compare_strings (const char *s, const char *t)
+{
+  if (s == NULL && t != NULL)
+    return 0;
+  else if (s != NULL && t == NULL)
+    return 0;
+  else if (s == NULL && t== NULL)
+    return 1;
+  return strcmp (s, t) == 0;
+}
+
+/* A helper function for typy_richcompare that checks two types for
+   "deep" equality.  Returns Py_EQ if the types are considered the
+   same, Py_NE otherwise.  */
+
+static int
+check_types_equal (struct type *type1, struct type *type2,
+		   VEC (type_equality_entry_d) **worklist)
+{
+  CHECK_TYPEDEF (type1);
+  CHECK_TYPEDEF (type2);
+
+  if (type1 == type2)
+    return Py_EQ;
+
+  if (TYPE_CODE (type1) != TYPE_CODE (type2)
+      || TYPE_LENGTH (type1) != TYPE_LENGTH (type2)
+      || TYPE_UNSIGNED (type1) != TYPE_UNSIGNED (type2)
+      || TYPE_NOSIGN (type1) != TYPE_NOSIGN (type2)
+      || TYPE_VARARGS (type1) != TYPE_VARARGS (type2)
+      || TYPE_VECTOR (type1) != TYPE_VECTOR (type2)
+      || TYPE_NOTTEXT (type1) != TYPE_NOTTEXT (type2)
+      || TYPE_INSTANCE_FLAGS (type1) != TYPE_INSTANCE_FLAGS (type2)
+      || TYPE_NFIELDS (type1) != TYPE_NFIELDS (type2))
+    return Py_NE;
+
+  if (!compare_strings (TYPE_TAG_NAME (type1), TYPE_TAG_NAME (type2)))
+    return Py_NE;
+  if (!compare_strings (TYPE_NAME (type1), TYPE_NAME (type2)))
+    return Py_NE;
+
+  if (TYPE_CODE (type1) == TYPE_CODE_RANGE)
+    {
+      if (memcmp (TYPE_RANGE_DATA (type1), TYPE_RANGE_DATA (type2),
+		  sizeof (*TYPE_RANGE_DATA (type1))) != 0)
+	return Py_NE;
+    }
+  else
+    {
+      int i;
+
+      for (i = 0; i < TYPE_NFIELDS (type1); ++i)
+	{
+	  const struct field *field1 = &TYPE_FIELD (type1, i);
+	  const struct field *field2 = &TYPE_FIELD (type2, i);
+	  struct type_equality_entry entry;
+
+	  if (FIELD_ARTIFICIAL (*field1) != FIELD_ARTIFICIAL (*field2)
+	      || FIELD_BITSIZE (*field1) != FIELD_BITSIZE (*field2)
+	      || FIELD_LOC_KIND (*field1) != FIELD_LOC_KIND (*field2))
+	    return Py_NE;
+	  if (!compare_strings (FIELD_NAME (*field1), FIELD_NAME (*field2)))
+	    return Py_NE;
+	  switch (FIELD_LOC_KIND (*field1))
+	    {
+	    case FIELD_LOC_KIND_BITPOS:
+	      if (FIELD_BITPOS (*field1) != FIELD_BITPOS (*field2))
+		return Py_NE;
+	      break;
+	    case FIELD_LOC_KIND_PHYSADDR:
+	      if (FIELD_STATIC_PHYSADDR (*field1)
+		  != FIELD_STATIC_PHYSADDR (*field2))
+		return Py_NE;
+	      break;
+	    case FIELD_LOC_KIND_PHYSNAME:
+	      if (!compare_strings (FIELD_STATIC_PHYSNAME (*field1),
+				    FIELD_STATIC_PHYSNAME (*field2)))
+		return Py_NE;
+	      break;
+	    }
+
+	  entry.type1 = FIELD_TYPE (*field1);
+	  entry.type2 = FIELD_TYPE (*field2);
+	  VEC_safe_push (type_equality_entry_d, *worklist, &entry);
+	}
+    }
+
+  if (TYPE_TARGET_TYPE (type1) != NULL)
+    {
+      struct type_equality_entry entry;
+      int added;
+
+      if (TYPE_TARGET_TYPE (type2) == NULL)
+	return Py_NE;
+
+      entry.type1 = TYPE_TARGET_TYPE (type1);
+      entry.type2 = TYPE_TARGET_TYPE (type2);
+      VEC_safe_push (type_equality_entry_d, *worklist, &entry);
+    }
+  else if (TYPE_TARGET_TYPE (type2) != NULL)
+    return Py_NE;
+
+  return Py_EQ;
+}
+
+/* Check types on a worklist for equality.  Returns Py_NE if any pair
+   is not equal, Py_EQ if they are all considered equal.  */
+
+static int
+check_types_worklist (VEC (type_equality_entry_d) **worklist,
+		      struct bcache *cache)
+{
+  while (!VEC_empty (type_equality_entry_d, *worklist))
+    {
+      struct type_equality_entry entry;
+      int added;
+
+      entry = *VEC_last (type_equality_entry_d, *worklist);
+      VEC_pop (type_equality_entry_d, *worklist);
+
+      /* If the type pair has already been visited, we know it is
+	 ok.  */
+      bcache_full (&entry, sizeof (entry), cache, &added);
+      if (!added)
+	continue;
+
+      if (check_types_equal (entry.type1, entry.type2, worklist) == Py_NE)
+	return Py_NE;
+    }
+
+  return Py_EQ;
+}
+
+/* Implement the richcompare method.  */
+
+static PyObject *
+typy_richcompare (PyObject *self, PyObject *other, int op)
+{
+  int result = Py_NE;
+  struct type *type1 = type_object_to_type (self);
+  struct type *type2 = type_object_to_type (other);
+  volatile struct gdb_exception except;
+
+  /* We can only compare ourselves to another Type object, and only
+     for equality or inequality.  */
+  if (type2 == NULL || (op != Py_EQ && op != Py_NE))
+    {
+      Py_INCREF (Py_NotImplemented);
+      return Py_NotImplemented;
+    }
+
+  if (type1 == type2)
+    result = Py_EQ;
+  else
+    {
+      struct bcache *cache;
+      VEC (type_equality_entry_d) *worklist;
+      struct type_equality_entry entry;
+
+      cache = bcache_xmalloc ();
+
+      entry.type1 = type1;
+      entry.type2 = type2;
+      VEC_safe_push (type_equality_entry_d, worklist, &entry);
+
+      TRY_CATCH (except, RETURN_MASK_ALL)
+	{
+	  result = check_types_worklist (&worklist, cache);
+	}
+      if (except.reason < 0)
+	result = Py_NE;
+
+      bcache_xfree (cache);
+      VEC_free (type_equality_entry_d, worklist);
+    }
+
+  if (op == result)
+    Py_RETURN_TRUE;
+  Py_RETURN_FALSE;
+}
+
 
 
 static const struct objfile_data *typy_objfile_data_key;
@@ -958,7 +1154,7 @@ static PyTypeObject type_object_type =
   "GDB type object",		  /* tp_doc */
   0,				  /* tp_traverse */
   0,				  /* tp_clear */
-  0,				  /* tp_richcompare */
+  typy_richcompare,		  /* tp_richcompare */
   0,				  /* tp_weaklistoffset */
   0,				  /* tp_iter */
   0,				  /* tp_iternext */