mathutils: Implement __hash__() functions

- all mathutils types
- only works on frozen data (so vectors can be used in sets/dict keys)
- uses same method as CPython, (matches hashing a tuple)

D1104 by @juicyfruit with own modifications

7 files changed, 122 insertions, 5 deletions

diff --git a/source/blender/python/mathutils/mathutils.c b/source/blender/python/mathutils/mathutils.c
index 28b2d26d3fd..7b51b08451b 100644
--- a/source/blender/python/mathutils/mathutils.c
+++ b/source/blender/python/mathutils/mathutils.c
@@ -79,6 +79,37 @@ static int mathutils_array_parse_fast(float *array,
 	return size;
 }
 
+/**
+ * helper function that returns a Python ``__hash__``.
+ *
+ * \note consistent with the equivalent tuple of floats (CPython's 'tuplehash')
+ */
+Py_hash_t mathutils_array_hash(const float *array, size_t array_len)
+{
+	int i;
+	Py_uhash_t x;  /* Unsigned for defined overflow behavior. */
+	Py_hash_t y;
+	Py_uhash_t mult;
+	Py_ssize_t len;
+
+	mult = _PyHASH_MULTIPLIER;
+	len = array_len;
+	x = 0x345678UL;
+	i = 0;
+	while (--len >= 0) {
+		y = _Py_HashDouble((double)(array[i++]));
+		if (y == -1)
+			return -1;
+		x = (x ^ y) * mult;
+		/* the cast might truncate len; that doesn't change hash stability */
+		mult += (Py_hash_t)(82520UL + len + len);
+	}
+	x += 97531UL;
+	if (x == (Py_uhash_t)-1)
+		x = -2;
+	return x;
+}
+
 /* helper functionm returns length of the 'value', -1 on error */
 int mathutils_array_parse(float *array, int array_min, int array_max, PyObject *value, const char *error_prefix)
 {
@@ -459,6 +490,13 @@ void _BaseMathObject_RaiseFrozenExc(const BaseMathObject *self)
 	             Py_TYPE(self)->tp_name);
 }
 
+void _BaseMathObject_RaiseNotFrozenExc(const BaseMathObject *self)
+{
+	PyErr_Format(PyExc_TypeError,
+	             "%s is not frozen (mutable), call freeze first",
+	             Py_TYPE(self)->tp_name);
+}
+
 /* BaseMathObject generic functions for all mathutils types */
 char BaseMathObject_owner_doc[] = "The item this is wrapping or None  (read-only).";
 PyObject *BaseMathObject_owner_get(BaseMathObject *self, void *UNUSED(closure))
diff --git a/source/blender/python/mathutils/mathutils.h b/source/blender/python/mathutils/mathutils.h
index 03ce9af3f49..e653b45389b 100644
--- a/source/blender/python/mathutils/mathutils.h
+++ b/source/blender/python/mathutils/mathutils.h
@@ -109,6 +109,7 @@ int _BaseMathObject_ReadIndexCallback(BaseMathObject *self, int index);
 int _BaseMathObject_WriteIndexCallback(BaseMathObject *self, int index);
 
 void _BaseMathObject_RaiseFrozenExc(const BaseMathObject *self);
+void _BaseMathObject_RaiseNotFrozenExc(const BaseMathObject *self);
 
 /* since this is called so often avoid where possible */
 #define BaseMath_ReadCallback(_self) \
@@ -133,12 +134,18 @@ void _BaseMathObject_RaiseFrozenExc(const BaseMathObject *self);
 	(UNLIKELY((_self)->flag & BASE_MATH_FLAG_IS_FROZEN) ? \
 	(_BaseMathObject_RaiseFrozenExc((BaseMathObject *)_self), -1) : 0)
 
+#define BaseMathObject_Prepare_ForHash(_self) \
+	(UNLIKELY(((_self)->flag & BASE_MATH_FLAG_IS_FROZEN) == 0) ? \
+	 (_BaseMathObject_RaiseNotFrozenExc((BaseMathObject *)_self), -1) : 0)
+
 /* utility func */
 int mathutils_array_parse(float *array, int array_min, int array_max, PyObject *value, const char *error_prefix);
 int mathutils_array_parse_alloc(float **array, int array_min, PyObject *value, const char *error_prefix);
 int mathutils_array_parse_alloc_v(float **array, int array_dim, PyObject *value, const char *error_prefix);
 int mathutils_any_to_rotmat(float rmat[3][3], PyObject *value, const char *error_prefix);
 
+Py_hash_t mathutils_array_hash(const float *float_array, size_t array_len);
+
 /* zero remaining unused elements of the array */
 #define MU_ARRAY_ZERO      (1 << 30)
 /* ignore larger py sequences than requested (just use first elements),
diff --git a/source/blender/python/mathutils/mathutils_Color.c b/source/blender/python/mathutils/mathutils_Color.c
index 7fea0e59b82..add8c2451ff 100644
--- a/source/blender/python/mathutils/mathutils_Color.c
+++ b/source/blender/python/mathutils/mathutils_Color.c
@@ -192,6 +192,17 @@ static PyObject *Color_richcmpr(PyObject *a, PyObject *b, int op)
 	return Py_INCREF_RET(res);
 }
 
+static Py_hash_t Color_hash(ColorObject *self)
+{
+	if (BaseMath_ReadCallback(self) == -1)
+		return -1;
+
+	if (BaseMathObject_Prepare_ForHash(self) == -1)
+		return -1;
+
+	return mathutils_array_hash(self->col, COLOR_SIZE);
+}
+
 /* ---------------------SEQUENCE PROTOCOLS------------------------ */
 /* ----------------------------len(object)------------------------ */
 /* sequence length */
@@ -843,7 +854,7 @@ PyTypeObject color_Type = {
 	&Color_NumMethods,              /* tp_as_number */
 	&Color_SeqMethods,              /* tp_as_sequence */
 	&Color_AsMapping,               /* tp_as_mapping */
-	NULL,                           /* tp_hash */
+	(hashfunc)Color_hash,           /* tp_hash */
 	NULL,                           /* tp_call */
 #ifndef MATH_STANDALONE
 	(reprfunc) Color_str,           /* tp_str */
diff --git a/source/blender/python/mathutils/mathutils_Euler.c b/source/blender/python/mathutils/mathutils_Euler.c
index ad761baf1ae..78532a1f75b 100644
--- a/source/blender/python/mathutils/mathutils_Euler.c
+++ b/source/blender/python/mathutils/mathutils_Euler.c
@@ -389,6 +389,17 @@ static PyObject *Euler_richcmpr(PyObject *a, PyObject *b, int op)
 	return Py_INCREF_RET(res);
 }
 
+static Py_hash_t Euler_hash(EulerObject *self)
+{
+	if (BaseMath_ReadCallback(self) == -1)
+		return -1;
+
+	if (BaseMathObject_Prepare_ForHash(self) == -1)
+		return -1;
+
+	return mathutils_array_hash(self->eul, EULER_SIZE);
+}
+
 /* ---------------------SEQUENCE PROTOCOLS------------------------ */
 /* ----------------------------len(object)------------------------ */
 /* sequence length */
@@ -696,7 +707,7 @@ PyTypeObject euler_Type = {
 	NULL,                           /* tp_as_number */
 	&Euler_SeqMethods,              /* tp_as_sequence */
 	&Euler_AsMapping,               /* tp_as_mapping */
-	NULL,                           /* tp_hash */
+	(hashfunc)Euler_hash,           /* tp_hash */
 	NULL,                           /* tp_call */
 #ifndef MATH_STANDALONE
 	(reprfunc) Euler_str,           /* tp_str */
diff --git a/source/blender/python/mathutils/mathutils_Matrix.c b/source/blender/python/mathutils/mathutils_Matrix.c
index 7b72ae5cebe..ce907091f65 100644
--- a/source/blender/python/mathutils/mathutils_Matrix.c
+++ b/source/blender/python/mathutils/mathutils_Matrix.c
@@ -895,6 +895,19 @@ static void matrix_copy(MatrixObject *mat_dst, const MatrixObject *mat_src)
 	memcpy(mat_dst->matrix, mat_src->matrix, sizeof(float) * (mat_dst->num_col * mat_dst->num_row));
 }
 
+/* transposes memory layout, rol/col's don't have to match */
+static void matrix_transpose_internal(float mat_dst_fl[], const MatrixObject *mat_src)
+{
+	unsigned short col, row;
+	unsigned int i = 0;
+
+	for (row = 0; row < mat_src->num_row; row++) {
+		for (col = 0; col < mat_src->num_col; col++) {
+			mat_dst_fl[i++] = MATRIX_ITEM(mat_src, row, col);
+		}
+	}
+}
+
 /* assumes rowsize == colsize is checked and the read callback has run */
 static float matrix_determinant_internal(const MatrixObject *self)
 {
@@ -2040,6 +2053,21 @@ static PyObject *Matrix_richcmpr(PyObject *a, PyObject *b, int op)
 	return Py_INCREF_RET(res);
 }
 
+static Py_hash_t Matrix_hash(MatrixObject *self)
+{
+	float mat[SQUARE(MATRIX_MAX_DIM)];
+
+	if (BaseMath_ReadCallback(self) == -1)
+		return -1;
+
+	if (BaseMathObject_Prepare_ForHash(self) == -1)
+		return -1;
+
+	matrix_transpose_internal(mat, self);
+
+	return mathutils_array_hash(mat, self->num_row * self->num_col);
+}
+
 /*---------------------SEQUENCE PROTOCOLS------------------------
  * ----------------------------len(object)------------------------
  * sequence length */
@@ -2745,7 +2773,7 @@ PyTypeObject matrix_Type = {
 	&Matrix_NumMethods,                 /*tp_as_number*/
 	&Matrix_SeqMethods,                 /*tp_as_sequence*/
 	&Matrix_AsMapping,                  /*tp_as_mapping*/
-	NULL,                               /*tp_hash*/
+	(hashfunc)Matrix_hash,              /*tp_hash*/
 	NULL,                               /*tp_call*/
 #ifndef MATH_STANDALONE
 	(reprfunc) Matrix_str,              /*tp_str*/
diff --git a/source/blender/python/mathutils/mathutils_Quaternion.c b/source/blender/python/mathutils/mathutils_Quaternion.c
index 8734d190f2f..e13255ba232 100644
--- a/source/blender/python/mathutils/mathutils_Quaternion.c
+++ b/source/blender/python/mathutils/mathutils_Quaternion.c
@@ -575,6 +575,17 @@ static PyObject *Quaternion_richcmpr(PyObject *a, PyObject *b, int op)
 	return Py_INCREF_RET(res);
 }
 
+static Py_hash_t Quaternion_hash(QuaternionObject *self)
+{
+	if (BaseMath_ReadCallback(self) == -1)
+		return -1;
+
+	if (BaseMathObject_Prepare_ForHash(self) == -1)
+		return -1;
+
+	return mathutils_array_hash(self->quat, QUAT_SIZE);
+}
+
 /* ---------------------SEQUENCE PROTOCOLS------------------------ */
 /* ----------------------------len(object)------------------------ */
 /* sequence length */
@@ -1275,7 +1286,7 @@ PyTypeObject quaternion_Type = {
 	&Quaternion_NumMethods,             /* tp_as_number */
 	&Quaternion_SeqMethods,             /* tp_as_sequence */
 	&Quaternion_AsMapping,              /* tp_as_mapping */
-	NULL,                               /* tp_hash */
+	(hashfunc)Quaternion_hash,          /* tp_hash */
 	NULL,                               /* tp_call */
 #ifndef MATH_STANDALONE
 	(reprfunc) Quaternion_str,          /* tp_str */
diff --git a/source/blender/python/mathutils/mathutils_Vector.c b/source/blender/python/mathutils/mathutils_Vector.c
index 91090e53e08..06d9a5c80dc 100644
--- a/source/blender/python/mathutils/mathutils_Vector.c
+++ b/source/blender/python/mathutils/mathutils_Vector.c
@@ -2051,6 +2051,17 @@ static PyObject *Vector_richcmpr(PyObject *objectA, PyObject *objectB, int compa
 	}
 }
 
+static Py_hash_t Vector_hash(VectorObject *self)
+{
+	if (BaseMath_ReadCallback(self) == -1)
+		return -1;
+
+	if (BaseMathObject_Prepare_ForHash(self) == -1)
+		return -1;
+
+	return mathutils_array_hash(self->vec, self->size);
+}
+
 /*-----------------PROTCOL DECLARATIONS--------------------------*/
 static PySequenceMethods Vector_SeqMethods = {
 	(lenfunc) Vector_len,               /* sq_length */
@@ -2927,7 +2938,7 @@ PyTypeObject vector_Type = {
 
 	/* More standard operations (here for binary compatibility) */
 
-	NULL,                       /* hashfunc tp_hash; */
+	(hashfunc)Vector_hash,      /* hashfunc tp_hash; */
 	NULL,                       /* ternaryfunc tp_call; */
 #ifndef MATH_STANDALONE
 	(reprfunc)Vector_str,       /* reprfunc tp_str; */