From f9ba2efe1e60fa919b0efe70994416149b54ee26 Mon Sep 17 00:00:00 2001 From: Emmanuel Leblond Date: Sat, 1 Feb 2020 07:04:14 +0100 Subject: Modify Dictionary::operator== to do real key/value comparison with recursive support (and add unittests) --- core/templates/ordered_hash_map.h | 6 ++- core/typedefs.h | 3 ++ core/variant/array.cpp | 66 +++++++++++++++++++++++++++--- core/variant/array.h | 3 ++ core/variant/dictionary.cpp | 62 ++++++++++++++++++++++++++--- core/variant/dictionary.h | 3 ++ core/variant/variant.cpp | 84 +++++++++++++++++++-------------------- core/variant/variant.h | 8 ++-- core/variant/variant_parser.cpp | 73 ++++++++++++++++++++-------------- core/variant/variant_parser.h | 2 +- core/variant/variant_setget.cpp | 12 ++++-- 11 files changed, 229 insertions(+), 93 deletions(-) (limited to 'core') diff --git a/core/templates/ordered_hash_map.h b/core/templates/ordered_hash_map.h index 7a17eeb644..4996b88190 100644 --- a/core/templates/ordered_hash_map.h +++ b/core/templates/ordered_hash_map.h @@ -207,8 +207,12 @@ public: (*list_element)->get().second = p_value; return Element(*list_element); } - typename InternalList::Element *new_element = list.push_back(Pair(nullptr, p_value)); + // Incorrectly set the first value of the pair with a value that will + // be invalid as soon as we leave this function... + typename InternalList::Element *new_element = list.push_back(Pair(&p_key, p_value)); + // ...this is needed here in case the hashmap recursively reference itself... typename InternalMap::Element *e = map.set(p_key, new_element); + // ...now we can set the right value ! new_element->get().first = &e->key(); return Element(new_element); diff --git a/core/typedefs.h b/core/typedefs.h index 8ca3d13e63..9ab874b2f0 100644 --- a/core/typedefs.h +++ b/core/typedefs.h @@ -277,6 +277,9 @@ struct BuildIndexSequence : BuildIndexSequence {}; template struct BuildIndexSequence<0, Is...> : IndexSequence {}; +// Limit the depth of recursive algorithms when dealing with Array/Dictionary +#define MAX_RECURSION 100 + #ifdef DEBUG_ENABLED #define DEBUG_METHODS_ENABLED #endif 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 &a1 = _p->array; + const Vector &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; diff --git a/core/variant/array.h b/core/variant/array.h index 4a1b25c4a9..bd39b8e0b1 100644 --- a/core/variant/array.h +++ b/core/variant/array.h @@ -63,8 +63,10 @@ public: bool operator==(const Array &p_array) const; bool operator!=(const Array &p_array) const; + bool recursive_equal(const Array &p_array, int recursion_count) const; uint32_t hash() const; + uint32_t recursive_hash(int recursion_count) const; void operator=(const Array &p_array); void push_back(const Variant &p_value); @@ -100,6 +102,7 @@ public: Variant pop_at(int p_pos); Array duplicate(bool p_deep = false) const; + Array recursive_duplicate(bool p_deep, int recursion_count) const; Array slice(int p_begin, int p_end, int p_step = 1, bool p_deep = false) const; Array filter(const Callable &p_callable) const; diff --git a/core/variant/dictionary.cpp b/core/variant/dictionary.cpp index 07b3a9a675..24d21386a7 100644 --- a/core/variant/dictionary.cpp +++ b/core/variant/dictionary.cpp @@ -188,11 +188,35 @@ bool Dictionary::erase(const Variant &p_key) { } bool Dictionary::operator==(const Dictionary &p_dictionary) const { - return _p == p_dictionary._p; + return recursive_equal(p_dictionary, 0); } bool Dictionary::operator!=(const Dictionary &p_dictionary) const { - return _p != p_dictionary._p; + return !recursive_equal(p_dictionary, 0); +} + +bool Dictionary::recursive_equal(const Dictionary &p_dictionary, int recursion_count) const { + // Cheap checks + if (_p == p_dictionary._p) { + return true; + } + if (_p->variant_map.size() != p_dictionary._p->variant_map.size()) { + return false; + } + + // Heavy O(n) check + if (recursion_count > MAX_RECURSION) { + ERR_PRINT("Max recursion reached"); + return true; + } + recursion_count++; + for (OrderedHashMap::ConstElement this_E = ((const OrderedHashMap *)&_p->variant_map)->front(); this_E; this_E = this_E.next()) { + OrderedHashMap::ConstElement other_E = ((const OrderedHashMap *)&p_dictionary._p->variant_map)->find(this_E.key()); + if (!other_E || !this_E.value().hash_compare(other_E.value(), recursion_count)) { + return false; + } + } + return true; } void Dictionary::_ref(const Dictionary &p_from) const { @@ -225,11 +249,21 @@ void Dictionary::_unref() const { } uint32_t Dictionary::hash() const { + return recursive_hash(0); +} + +uint32_t Dictionary::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::DICTIONARY); + recursion_count++; for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { - h = hash_djb2_one_32(E.key().hash(), h); - h = hash_djb2_one_32(E.value().hash(), h); + h = hash_djb2_one_32(E.key().recursive_hash(recursion_count), h); + h = hash_djb2_one_32(E.value().recursive_hash(recursion_count), h); } return h; @@ -286,10 +320,26 @@ const Variant *Dictionary::next(const Variant *p_key) const { } Dictionary Dictionary::duplicate(bool p_deep) const { + return recursive_duplicate(p_deep, 0); +} + +Dictionary Dictionary::recursive_duplicate(bool p_deep, int recursion_count) const { Dictionary n; - for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { - n[E.key()] = p_deep ? E.value().duplicate(true) : E.value(); + if (recursion_count > MAX_RECURSION) { + ERR_PRINT("Max recursion reached"); + return n; + } + + if (p_deep) { + recursion_count++; + for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { + n[E.key().recursive_duplicate(true, recursion_count)] = E.value().recursive_duplicate(true, recursion_count); + } + } else { + for (OrderedHashMap::Element E = _p->variant_map.front(); E; E = E.next()) { + n[E.key()] = E.value(); + } } return n; diff --git a/core/variant/dictionary.h b/core/variant/dictionary.h index 4067ff9fd9..f8a2a7573f 100644 --- a/core/variant/dictionary.h +++ b/core/variant/dictionary.h @@ -70,8 +70,10 @@ public: bool operator==(const Dictionary &p_dictionary) const; bool operator!=(const Dictionary &p_dictionary) const; + bool recursive_equal(const Dictionary &p_dictionary, int recursion_count) const; uint32_t hash() const; + uint32_t recursive_hash(int recursion_count) const; void operator=(const Dictionary &p_dictionary); const Variant *next(const Variant *p_key = nullptr) const; @@ -80,6 +82,7 @@ public: Array values() const; Dictionary duplicate(bool p_deep = false) const; + Dictionary recursive_duplicate(bool p_deep, int recursion_count) const; const void *id() const; diff --git a/core/variant/variant.cpp b/core/variant/variant.cpp index 1d70d4c506..c43ff8626e 100644 --- a/core/variant/variant.cpp +++ b/core/variant/variant.cpp @@ -784,16 +784,11 @@ bool Variant::can_convert_strict(Variant::Type p_type_from, Variant::Type p_type } bool Variant::operator==(const Variant &p_variant) const { - if (type != p_variant.type) { //evaluation of operator== needs to be more strict - return false; - } - bool v; - Variant r; - evaluate(OP_EQUAL, *this, p_variant, r, v); - return r; + return hash_compare(p_variant); } bool Variant::operator!=(const Variant &p_variant) const { + // Don't use `!hash_compare(p_variant)` given it makes use of OP_EQUAL if (type != p_variant.type) { //evaluation of operator== needs to be more strict return true; } @@ -1617,25 +1612,23 @@ struct _VariantStrPair { }; Variant::operator String() const { - List stack; - - return stringify(stack); + return stringify(0); } template -String stringify_vector(const T &vec, List &stack) { +String stringify_vector(const T &vec, int recursion_count) { String str("["); for (int i = 0; i < vec.size(); i++) { if (i > 0) { str += ", "; } - str = str + Variant(vec[i]).stringify(stack); + str = str + Variant(vec[i]).stringify(recursion_count); } str += "]"; return str; } -String Variant::stringify(List &stack) const { +String Variant::stringify(int recursion_count) const { switch (type) { case NIL: return "null"; @@ -1679,23 +1672,22 @@ String Variant::stringify(List &stack) const { return operator Color(); case DICTIONARY: { const Dictionary &d = *reinterpret_cast(_data._mem); - if (stack.find(d.id())) { + if (recursion_count > MAX_RECURSION) { + ERR_PRINT("Max recursion reached"); return "{...}"; } - stack.push_back(d.id()); - - //const String *K=nullptr; String str("{"); List keys; d.get_key_list(&keys); Vector<_VariantStrPair> pairs; - for (const Variant &E : keys) { + recursion_count++; + for (List::Element *E = keys.front(); E; E = E->next()) { _VariantStrPair sp; - sp.key = E.stringify(stack); - sp.value = d[E].stringify(stack); + sp.key = E->get().stringify(recursion_count); + sp.value = d[E->get()].stringify(recursion_count); pairs.push_back(sp); } @@ -1710,46 +1702,43 @@ String Variant::stringify(List &stack) const { } str += "}"; - stack.erase(d.id()); return str; } break; case PACKED_VECTOR2_ARRAY: { - return stringify_vector(operator Vector(), stack); + return stringify_vector(operator Vector(), recursion_count); } break; case PACKED_VECTOR3_ARRAY: { - return stringify_vector(operator Vector(), stack); + return stringify_vector(operator Vector(), recursion_count); } break; case PACKED_COLOR_ARRAY: { - return stringify_vector(operator Vector(), stack); + return stringify_vector(operator Vector(), recursion_count); } break; case PACKED_STRING_ARRAY: { - return stringify_vector(operator Vector(), stack); + return stringify_vector(operator Vector(), recursion_count); } break; case PACKED_BYTE_ARRAY: { - return stringify_vector(operator Vector(), stack); + return stringify_vector(operator Vector(), recursion_count); } break; case PACKED_INT32_ARRAY: { - return stringify_vector(operator Vector(), stack); + return stringify_vector(operator Vector(), recursion_count); } break; case PACKED_INT64_ARRAY: { - return stringify_vector(operator Vector(), stack); + return stringify_vector(operator Vector(), recursion_count); } break; case PACKED_FLOAT32_ARRAY: { - return stringify_vector(operator Vector(), stack); + return stringify_vector(operator Vector(), recursion_count); } break; case PACKED_FLOAT64_ARRAY: { - return stringify_vector(operator Vector(), stack); + return stringify_vector(operator Vector(), recursion_count); } break; case ARRAY: { Array arr = operator Array(); - if (stack.find(arr.id())) { + if (recursion_count > MAX_RECURSION) { + ERR_PRINT("Max recursion reached"); return "[...]"; } - stack.push_back(arr.id()); - String str = stringify_vector(arr, stack); - - stack.erase(arr.id()); + String str = stringify_vector(arr, recursion_count); return str; } break; @@ -2768,6 +2757,10 @@ Variant::Variant(const Variant &p_variant) { } uint32_t Variant::hash() const { + return recursive_hash(0); +} + +uint32_t Variant::recursive_hash(int recursion_count) const { switch (type) { case NIL: { return 0; @@ -2895,7 +2888,7 @@ uint32_t Variant::hash() const { return reinterpret_cast(_data._mem)->hash(); } break; case DICTIONARY: { - return reinterpret_cast(_data._mem)->hash(); + return reinterpret_cast(_data._mem)->recursive_hash(recursion_count); } break; case CALLABLE: { @@ -2909,7 +2902,7 @@ uint32_t Variant::hash() const { } break; case ARRAY: { const Array &arr = *reinterpret_cast(_data._mem); - return arr.hash(); + return arr.recursive_hash(recursion_count); } break; case PACKED_BYTE_ARRAY: { @@ -3083,7 +3076,7 @@ uint32_t Variant::hash() const { \ return true -bool Variant::hash_compare(const Variant &p_variant) const { +bool Variant::hash_compare(const Variant &p_variant, int recursion_count) const { if (type != p_variant.type) { return false; } @@ -3214,14 +3207,19 @@ bool Variant::hash_compare(const Variant &p_variant) const { const Array &l = *(reinterpret_cast(_data._mem)); const Array &r = *(reinterpret_cast(p_variant._data._mem)); - if (l.size() != r.size()) { + if (!l.recursive_equal(r, recursion_count + 1)) { return false; } - for (int i = 0; i < l.size(); ++i) { - if (!l[i].hash_compare(r[i])) { - return false; - } + return true; + } break; + + case DICTIONARY: { + const Dictionary &l = *(reinterpret_cast(_data._mem)); + const Dictionary &r = *(reinterpret_cast(p_variant._data._mem)); + + if (!l.recursive_equal(r, recursion_count + 1)) { + return false; } return true; diff --git a/core/variant/variant.h b/core/variant/variant.h index d3f694e7ca..8ce5e7dcd2 100644 --- a/core/variant/variant.h +++ b/core/variant/variant.h @@ -481,7 +481,8 @@ public: static PTROperatorEvaluator get_ptr_operator_evaluator(Operator p_operator, Type p_type_a, Type p_type_b); void zero(); - Variant duplicate(bool deep = false) const; + Variant duplicate(bool p_deep = false) const; + Variant recursive_duplicate(bool p_deep, int recursion_count) const; static void blend(const Variant &a, const Variant &b, float c, Variant &r_dst); static void interpolate(const Variant &a, const Variant &b, float c, Variant &r_dst); @@ -659,10 +660,11 @@ public: bool operator!=(const Variant &p_variant) const; bool operator<(const Variant &p_variant) const; uint32_t hash() const; + uint32_t recursive_hash(int recursion_count) const; - bool hash_compare(const Variant &p_variant) const; + bool hash_compare(const Variant &p_variant, int recursion_count = 0) const; bool booleanize() const; - String stringify(List &stack) const; + String stringify(int recursion_count = 0) const; String to_json_string() const; void static_assign(const Variant &p_variant); diff --git a/core/variant/variant_parser.cpp b/core/variant/variant_parser.cpp index 221a8c4f98..3c19c2c706 100644 --- a/core/variant/variant_parser.cpp +++ b/core/variant/variant_parser.cpp @@ -1443,7 +1443,7 @@ static String rtos_fix(double p_value) { } } -Error VariantWriter::write(const Variant &p_variant, StoreStringFunc p_store_string_func, void *p_store_string_ud, EncodeResourceFunc p_encode_res_func, void *p_encode_res_ud) { +Error VariantWriter::write(const Variant &p_variant, StoreStringFunc p_store_string_func, void *p_store_string_ud, EncodeResourceFunc p_encode_res_func, void *p_encode_res_ud, int recursion_count) { switch (p_variant.get_type()) { case Variant::NIL: { p_store_string_func(p_store_string_ud, "null"); @@ -1639,41 +1639,56 @@ Error VariantWriter::write(const Variant &p_variant, StoreStringFunc p_store_str case Variant::DICTIONARY: { Dictionary dict = p_variant; - - List keys; - dict.get_key_list(&keys); - keys.sort(); - - p_store_string_func(p_store_string_ud, "{\n"); - for (List::Element *E = keys.front(); E; E = E->next()) { - /* - if (!_check_type(dict[E])) - continue; - */ - write(E->get(), p_store_string_func, p_store_string_ud, p_encode_res_func, p_encode_res_ud); - p_store_string_func(p_store_string_ud, ": "); - write(dict[E->get()], p_store_string_func, p_store_string_ud, p_encode_res_func, p_encode_res_ud); - if (E->next()) { - p_store_string_func(p_store_string_ud, ",\n"); - } else { - p_store_string_func(p_store_string_ud, "\n"); + if (recursion_count > MAX_RECURSION) { + ERR_PRINT("Max recursion reached"); + p_store_string_func(p_store_string_ud, "{}"); + } else { + recursion_count++; + + List keys; + dict.get_key_list(&keys); + keys.sort(); + + p_store_string_func(p_store_string_ud, "{\n"); + for (List::Element *E = keys.front(); E; E = E->next()) { + /* + if (!_check_type(dict[E->get()])) + continue; + */ + write(E->get(), p_store_string_func, p_store_string_ud, p_encode_res_func, p_encode_res_ud, recursion_count); + p_store_string_func(p_store_string_ud, ": "); + write(dict[E->get()], p_store_string_func, p_store_string_ud, p_encode_res_func, p_encode_res_ud, recursion_count); + if (E->next()) { + p_store_string_func(p_store_string_ud, ",\n"); + } else { + p_store_string_func(p_store_string_ud, "\n"); + } } - } - p_store_string_func(p_store_string_ud, "}"); + p_store_string_func(p_store_string_ud, "}"); + } } break; + case Variant::ARRAY: { - p_store_string_func(p_store_string_ud, "["); - Array array = p_variant; - int len = array.size(); - for (int i = 0; i < len; i++) { - if (i > 0) { - p_store_string_func(p_store_string_ud, ", "); + if (recursion_count > MAX_RECURSION) { + ERR_PRINT("Max recursion reached"); + p_store_string_func(p_store_string_ud, "[]"); + } else { + recursion_count++; + + p_store_string_func(p_store_string_ud, "["); + Array array = p_variant; + int len = array.size(); + for (int i = 0; i < len; i++) { + if (i > 0) { + p_store_string_func(p_store_string_ud, ", "); + } + write(array[i], p_store_string_func, p_store_string_ud, p_encode_res_func, p_encode_res_ud, recursion_count); } - write(array[i], p_store_string_func, p_store_string_ud, p_encode_res_func, p_encode_res_ud); + + p_store_string_func(p_store_string_ud, "]"); } - p_store_string_func(p_store_string_ud, "]"); } break; diff --git a/core/variant/variant_parser.h b/core/variant/variant_parser.h index 1ba26db6ed..2e4baa6fff 100644 --- a/core/variant/variant_parser.h +++ b/core/variant/variant_parser.h @@ -140,7 +140,7 @@ public: typedef Error (*StoreStringFunc)(void *ud, const String &p_string); typedef String (*EncodeResourceFunc)(void *ud, const RES &p_resource); - static Error write(const Variant &p_variant, StoreStringFunc p_store_string_func, void *p_store_string_ud, EncodeResourceFunc p_encode_res_func, void *p_encode_res_ud); + static Error write(const Variant &p_variant, StoreStringFunc p_store_string_func, void *p_store_string_ud, EncodeResourceFunc p_encode_res_func, void *p_encode_res_ud, int recursion_count = 0); static Error write_to_string(const Variant &p_variant, String &r_string, EncodeResourceFunc p_encode_res_func = nullptr, void *p_encode_res_ud = nullptr); }; diff --git a/core/variant/variant_setget.cpp b/core/variant/variant_setget.cpp index 4abb51ca7c..2530d77c62 100644 --- a/core/variant/variant_setget.cpp +++ b/core/variant/variant_setget.cpp @@ -1824,11 +1824,15 @@ Variant Variant::iter_get(const Variant &r_iter, bool &r_valid) const { return Variant(); } -Variant Variant::duplicate(bool deep) const { +Variant Variant::duplicate(bool p_deep) const { + return recursive_duplicate(p_deep, 0); +} + +Variant Variant::recursive_duplicate(bool p_deep, int recursion_count) const { switch (type) { case OBJECT: { /* breaks stuff :( - if (deep && !_get_obj().ref.is_null()) { + if (p_deep && !_get_obj().ref.is_null()) { Ref resource = _get_obj().ref; if (resource.is_valid()) { return resource->duplicate(true); @@ -1838,9 +1842,9 @@ Variant Variant::duplicate(bool deep) const { return *this; } break; case DICTIONARY: - return operator Dictionary().duplicate(deep); + return operator Dictionary().recursive_duplicate(p_deep, recursion_count); case ARRAY: - return operator Array().duplicate(deep); + return operator Array().recursive_duplicate(p_deep, recursion_count); case PACKED_BYTE_ARRAY: return operator Vector().duplicate(); case PACKED_INT32_ARRAY: -- cgit v1.2.3