Merge pull request #35816 from touilleMan/dictionary-operator==-true-comparison

Modify Array/Dictionary::operator== to do real key/value comparison

1 files changed, 60 insertions, 6 deletions

diff --git a/core/variant/array.cpp b/core/variant/array.cpp
index b4d6dffc6f..69a0fff1a1 100644
--- a/core/variant/array.cpp
+++ b/core/variant/array.cpp
@@ -97,11 +97,38 @@ void Array::clear() {
 }
 
 bool Array::operator==(const Array &p_array) const {
-	return _p == p_array._p;
+	return recursive_equal(p_array, 0);
 }
 
 bool Array::operator!=(const Array &p_array) const {
-	return !operator==(p_array);
+	return !recursive_equal(p_array, 0);
+}
+
+bool Array::recursive_equal(const Array &p_array, int recursion_count) const {
+	// Cheap checks
+	if (_p == p_array._p) {
+		return true;
+	}
+	const Vector<Variant> &a1 = _p->array;
+	const Vector<Variant> &a2 = p_array._p->array;
+	const int size = a1.size();
+	if (size != a2.size()) {
+		return false;
+	}
+
+	// Heavy O(n) check
+	if (recursion_count > MAX_RECURSION) {
+		ERR_PRINT("Max recursion reached");
+		return true;
+	}
+	recursion_count++;
+	for (int i = 0; i < size; i++) {
+		if (!a1[i].hash_compare(a2[i], recursion_count)) {
+			return false;
+		}
+	}
+
+	return true;
 }
 
 bool Array::operator<(const Array &p_array) const {
@@ -132,10 +159,20 @@ bool Array::operator>=(const Array &p_array) const {
 }
 
 uint32_t Array::hash() const {
-	uint32_t h = hash_djb2_one_32(0);
+	return recursive_hash(0);
+}
 
+uint32_t Array::recursive_hash(int recursion_count) const {
+	if (recursion_count > MAX_RECURSION) {
+		ERR_PRINT("Max recursion reached");
+		return 0;
+	}
+
+	uint32_t h = hash_djb2_one_32(Variant::ARRAY);
+
+	recursion_count++;
 	for (int i = 0; i < _p->array.size(); i++) {
-		h = hash_djb2_one_32(_p->array[i].hash(), h);
+		h = hash_djb2_one_32(_p->array[i].recursive_hash(recursion_count), h);
 	}
 	return h;
 }
@@ -300,12 +337,29 @@ const Variant &Array::get(int p_idx) const {
 }
 
 Array Array::duplicate(bool p_deep) const {
+	return recursive_duplicate(p_deep, 0);
+}
+
+Array Array::recursive_duplicate(bool p_deep, int recursion_count) const {
 	Array new_arr;
+
+	if (recursion_count > MAX_RECURSION) {
+		ERR_PRINT("Max recursion reached");
+		return new_arr;
+	}
+
 	int element_count = size();
 	new_arr.resize(element_count);
 	new_arr._p->typed = _p->typed;
-	for (int i = 0; i < element_count; i++) {
-		new_arr[i] = p_deep ? get(i).duplicate(p_deep) : get(i);
+	if (p_deep) {
+		recursion_count++;
+		for (int i = 0; i < element_count; i++) {
+			new_arr[i] = get(i).recursive_duplicate(true, recursion_count);
+		}
+	} else {
+		for (int i = 0; i < element_count; i++) {
+			new_arr[i] = get(i);
+		}
 	}
 
 	return new_arr;